궤도
[백준] 19236번 : 청소년 상어 본문
문제
풀이
할 일을 정리해보자...
1. 상어가 위치한 곳에 있는 물고기를 먹음
1.1 상어의 위치, 방향 정보 갱신
1.2 물고기 삭제 처리
1.3 상어의 새로운 위치를 공간에 기록
2. 1~16번 물고기 이동(아직 살아있는 물고기만)
3. 상어가 이동할 수 있는 모든 공간 탐색(백트래킹 재귀 함수)
3.1 상어가 더 이상 이동할 수 없으면 최댓값 갱신
공간의 현재 상태를 기록할 4x4 2차원 배열과 상어+물고기의 위치, 방향 정보를 기록할 1차원 배열이 필요하다.
상어는 여러 칸을 이동할 수 있지만 방향을 바꿀 수 없고, 물고기는 한 칸만 이동할 수 있지만 방향을 바꿀 수 있다는 차이점을 염두해야 한다.
소스코드
#include <iostream>
#include <vector>
using namespace std;
struct info {
int r, c, d;
};
int max_fish = 0;
pair<int, int> direction[8] = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};
void moveFish(int idx, vector<info> &pos, vector<vector<int>> &board) {
int row = pos[idx].r, col = pos[idx].c, dir = pos[idx].d; //행, 열, 방향
do {
int nr = row + direction[dir].first;
int nc = col + direction[dir].second;
if ((nr >= 0) && (nr < 4) && (nc >= 0) && (nc < 4) && (board[nr][nc] != 0)) { //범위내에 있고 상어 없으면
swap(board[row][col], board[nr][nc]); //위치 교환
pos[idx] = {nr, nc, dir}; //이번에 이동한 물고기 정보 갱신
if (board[row][col] != -1) //빈공간으로 이동한게 아니라면(물고기와 위치를 바꾼거라면)
pos[board[row][col]] = {row, col, pos[board[row][col]].d}; //바뀐 물고기 정보 갱신
break;
}
dir = (dir + 1) % 8; //방향 바꾸기
} while (dir != pos[idx].d);
}
void backtracking(int r, int c, int fish, vector<info> pos, vector<vector<int>> board) {
fish += board[r][c]; //물고기 먹음
int dir = pos[board[r][c]].d; //먹은 물고기의 방향
pos[0] = {r, c, dir}; //상어 정보 갱신
pos[board[r][c]].d = -1; //먹힌 물고기 갱신
board[r][c] = 0; //상어 위치 표시
for (int i = 1; i <= 16; i++) {
if (pos[i].d != -1) //먹힌 물고기가 아니라면 이동
moveFish(i, pos, board);
}
int nr = r, nc = c;
while (true) { //범위 벗어날 때까지 해당 방향으로 이동
nr += direction[dir].first;
nc += direction[dir].second;
if ((nr < 0) || (nr >= 4) || (nc < 0) || (nc >= 4)) //범위 벗어남
break;
if (board[nr][nc] != -1) { //물고기가 존재
board[r][c] = -1; //원래 상어가 있던 곳은 빈공간으로
backtracking(nr, nc, fish, pos, board);
}
}
max_fish = max(max_fish, fish); //최댓값 갱신
}
int main() {
vector<vector<int>> board(4, vector<int>(4));
vector<info> pos(17);
int a, b;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cin >> a >> b;
board[i][j] = a;
pos[a] = {i, j, b - 1};
}
}
backtracking(0, 0, 0, pos, board);
cout << max_fish;
}전체 소스코드다.
struct info {
int r, c, d;
};
int max_fish = 0;
pair<int, int> direction[8] = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};물고기, 상어의 정보를 저장할 info 구조체와 먹을 물고기 번호의 최댓값을 저장할 max_fish 변수,
그리고 8개의 방향이다.
vector<vector<int>> board(4, vector<int>(4));
vector<info> pos(17);
int a, b;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cin >> a >> b;
board[i][j] = a;
pos[a] = {i, j, b - 1};
}
}물고기가 16마리 상어가 1마리니까 pos 벡터는 17만큼 할당하고 board 2차원 벡터는 4x4로 만든다.
그리고 입력을 받는데, 방향이 0~7이 되도록 b-1을 해준다.
backtracking(0, 0, 0, pos, board);함수 호출...시작점은 (0, 0)이고 먹은 물고기의 수는 0이다.
void backtracking(int r, int c, int fish, vector<info> pos, vector<vector<int>> board) {
fish += board[r][c]; //물고기 먹음
int dir = pos[board[r][c]].d; //먹은 물고기의 방향
pos[0] = {r, c, dir}; //상어 정보 갱신
pos[board[r][c]].d = -1; //먹힌 물고기 갱신
board[r][c] = 0; //상어 위치 표시
for (int i = 1; i <= 16; i++) {
if (pos[i].d != -1) //먹힌 물고기가 아니라면 이동
moveFish(i, pos, board);
}
int nr = r, nc = c;
while (true) { //범위 벗어날 때까지 해당 방향으로 이동
nr += direction[dir].first;
nc += direction[dir].second;
if ((nr < 0) || (nr >= 4) || (nc < 0) || (nc >= 4)) //범위 벗어남
break;
if (board[nr][nc] != -1) { //물고기가 존재
board[r][c] = -1; //원래 상어가 있던 곳은 빈공간으로
backtracking(nr, nc, fish, pos, board);
}
}
max_fish = max(max_fish, fish); //최댓값 갱신
}원래는 백트래킹에서 unvisited 처리를 할 때 pos와 board를 복사해놓고 다시 쓰는 방법으로 구현할까 했는데, 귀찮아서 그냥 파라미터로 넘기기로 했다.
fish += board[r][c]; //물고기 먹음
int dir = pos[board[r][c]].d; //먹은 물고기의 방향
pos[0] = {r, c, dir}; //상어 정보 갱신
pos[board[r][c]].d = -1; //먹힌 물고기 갱신
board[r][c] = 0; //상어 위치 표시먼저 물고기를 먹었으니 fish 변수를 갱신하고, 해당 물고기의 방향을 저장해둔다.
그리고 그에 맞춰 상어의 행, 열, 방향 정보를 갱신하고, 먹힌 물고기의 방향을 -1로 바꿔준다. 먹혔다는 뜻이다.
마지막으로 원래 물고기가 있던 자리를 0으로 갱신해서 상어가 있다고 표시한다.
for (int i = 1; i <= 16; i++) {
if (pos[i].d != -1) //먹힌 물고기가 아니라면 이동
moveFish(i, pos, board);
}모든 물고기에 대해 방향 정보가 -1이 아니라면, 그니까 먹힌 물고기가 아니라면 moveFish를 통해 움직여준다.
void moveFish(int idx, vector<info> &pos, vector<vector<int>> &board) {
int row = pos[idx].r, col = pos[idx].c, dir = pos[idx].d; //행, 열, 방향
do {
int nr = row + direction[dir].first;
int nc = col + direction[dir].second;
if ((nr >= 0) && (nr < 4) && (nc >= 0) && (nc < 4) && (board[nr][nc] != 0)) { //범위내에 있고 상어 없으면
swap(board[row][col], board[nr][nc]); //위치 교환
pos[idx] = {nr, nc, dir}; //이번에 이동한 물고기 정보 갱신
if (board[row][col] != -1) //빈공간으로 이동한게 아니라면(물고기와 위치를 바꾼거라면)
pos[board[row][col]] = {row, col, pos[board[row][col]].d}; //바뀐 물고기 정보 갱신
break;
}
dir = (dir + 1) % 8; //방향 바꾸기
} while (dir != pos[idx].d);
}방향을 옮길 수 있는 횟수는 최대 8번이다.
int nr = row + direction[dir].first;
int nc = col + direction[dir].second;
if ((nr >= 0) && (nr < 4) && (nc >= 0) && (nc < 4) && (board[nr][nc] != 0)) { //범위내에 있고 상어 없으면
swap(board[row][col], board[nr][nc]); //위치 교환
pos[idx] = {nr, nc, dir}; //이번에 이동한 물고기 정보 갱신
if (board[row][col] != -1) //빈공간으로 이동한게 아니라면(물고기와 위치를 바꾼거라면)
pos[board[row][col]] = {row, col, pos[board[row][col]].d}; //바뀐 물고기 정보 갱신
break;
}
dir = (dir + 1) % 8; //방향 바꾸기dir 방향으로 1칸 움직인 nr, nc에 대해, 이게 범위 내에 있고 그 자리에 상어가 있는게 아니라면
swap으로 위치를 교환한다. 이동하게 될 공간이 빈 공간이라도 상관없다. 어차피 해당 물고기가 빈 공간으로 이동하게 되면 물고기가 있던 곳이 새로운 빈 공간이 될 것이기 때문에 -1과 swap하는 셈이다.
swap을 하면 board의 상태만 갱신되는 것이니, pos[idx]도 갱신하고 만약 물고기와 자리를 바꾼거라면 바뀐 물고기의 위치 정보도 갱신한다.
만약 범위를 벗어나거나 상어가 있어서 이동하지 못했다면 dir값을 갱신하면서 다음 방향을 살펴본다.
int nr = r, nc = c;
while (true) { //범위 벗어날 때까지 해당 방향으로 이동
nr += direction[dir].first;
nc += direction[dir].second;
if ((nr < 0) || (nr >= 4) || (nc < 0) || (nc >= 4)) //범위 벗어남
break;
if (board[nr][nc] != -1) { //물고기가 존재
board[r][c] = -1; //원래 상어가 있던 곳은 빈공간으로
backtracking(nr, nc, fish, pos, board);
}
}물고기가 전부 이동했으니 상어를 움직일 차례다.
상어의 방향으로 한칸씩 움직여보면서 물고기가 존재하는 칸이라면 원래 상어가 있던 곳을 빈공간으로 바꿔준 뒤, 새로운 좌표에 대해 재귀함수를 호출한다.
max_fish = max(max_fish, fish); //최댓값 갱신가능한 모든 칸을 탐색한 뒤엔 최댓값을 갱신한다.
