개발 블로그

문제 링크 : www.acmicpc.net/problem/19236

문제

아기 상어가 성장해 청소년 상어가 되었다.

4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.

오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.

물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

<그림 1>

<그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다. 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다. <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.

<그림 2>

이제 물고기가 이동해야 한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다. 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다. 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.

<그림 3>

2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다. 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.

<그림 4>

3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다. 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다. ← 방향에는 상어가 있으니 또 회전을 해야 한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다. 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.

<그림 5>

물고기가 모두 이동했으니 이제 상어가 이동할 순서이다. 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다. 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.

<그림 6>

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

입력

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

접근 방법

이 문제의 핵심은

상어가 잡아먹을 물고기 칸을 선택할 때, 여러 칸 중 하나를 선택할 수 있으며, 각 선택에 따라 배열 상태가 모두 달라지며 또 그 바뀐 배열에 대해 여러 갈래로 선택지가 나눠진다는 것이다. 이때 가지를 쳐가면서 진행했다가 다시 돌아와야하며 진행 전의 상태로 돌아가야 하는데 이를 어떻게 구현해야할지 어려웠다.

그래서 해설을 보고 풀어보았다. 

보통 다른 DFS 알고리즘에서 백트래킹을 할 때는 vector에서 pop 해주는 방식으로 구현했었는데 이 문제에서는 물고기 번호를 나타내는 이차원 배열과 물고기 객체 정보를 담고 있는 1차원 배열, 이 두개의 상태를 저장해줘야 해서 어려웠던것 같다. 

그래서 이 문제에서 백트래킹을 구현하기 위해 배열을 복사해서, 복사한 배열의 상태를 변화시켜보고 그 바꾼 배열을 파라미터로 넘겨줌으로써 진행시켜나간다. 이렇게 하면 가지쳐 나간 단계를 한 단계 돌아왔을 때 기존의 배열은 그대로 있기 때문에 이전 단계의 상태를 KEEP 할 수 있게 된다. 

또 하나 주의할 점은 12시 방향을 의미하는 회전 번호가 1이기 때문에,

처음에 입력받아서 방향 정보를 저장할 때, 1 감소 후 저장하도록 한다. 

이렇게 하면 mod 8 연산을 이용한 방향 회전 구현에 용이하다.  

#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
using namespace std;


class Fish {
public:
	int num, dir, r, c;
	bool live;
	Fish(){}
	Fish(int _n, int _d, int _r, int _c, bool _live) {
		num = _n; 
		dir = _d;
		r = _r;
		c = _c;
		live = _live;
	}
};

Fish fishArr[17];	//물고기 1~ 16번까지 객체 저장
int map[4][4];		//물고기 번호만 저장

//12,11,9,,,
int dr[8] = { -1,-1,0,1,1,1,0,-1 };
int dc[8] = { 0,-1,-1,-1,0,1,1,1 };


int ret = 0;

//배열을 함수의 파라미터로 넘길시 Call By Reference (주소값만 넘어감)
void solveDFS(int map[][4], Fish fishArr[], int shark_row, int shark_col, int s) {	

	//백트래킹을 위해 기존 배열 놔두고 카피해서 상태변화 시켜봄
	int copy_map[4][4];
	Fish copy_fishArr[17];
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			copy_map[i][j] = map[i][j];
		}
	}
	for (int i = 0; i < 17; i++ ) {
		copy_fishArr[i] = fishArr[i];
	}


	//물고기 잡아먹기
	int fishNum = copy_map[shark_row][shark_col];
	int shark_dir = copy_fishArr[fishNum].dir;				//잡아먹은 물고기 방향으로 바뀜
	copy_fishArr[fishNum].live = false;
	copy_map[shark_row][shark_col] = -1;						//물고기 잡아먹어서 물고기 없어짐

	s += fishNum;
	if (ret < s) ret = s;




	//물고기 이동
	for (int f = 1; f <= 16; f++) {
		if (copy_fishArr[f].live == false) continue;

		//현재 순서인 물고기의 위치
		int cr = copy_fishArr[f].r;
		int cc = copy_fishArr[f].c;
		int cd = copy_fishArr[f].dir;

		//바꿀 타겟의 위치
		int nr = cr + dr[cd];
		int nc = cc + dc[cd];
		int nd = cd;

		//타겟이 범위 넘어가거나 상어면 회전
		while (nr < 0 || nr >= 4 || nc < 0 || nc >= 4 || (nr == shark_row && nc == shark_col)) {
			nd = (nd + 1) % 8;
			nr = cr + dr[nd];
			nc = cc + dc[nd];
		}

		//1. 타겟 칸이 물고기면

		if (copy_map[nr][nc] != -1) {
			int targetFishNum = copy_map[nr][nc];
			//타겟 물고기 위치 갱신
			copy_fishArr[targetFishNum].r = cr;
			copy_fishArr[targetFishNum].c = cc;

			//현재 물고기 위치 갱신
			copy_fishArr[f].r = nr;
			copy_fishArr[f].c = nc;
			copy_fishArr[f].dir = nd;

			//이차원 배열 번호 swap
			copy_map[nr][nc] = f;
			copy_map[cr][cc] = targetFishNum;

		}


		//2. 타겟 칸이 빈칸이면
		else {

			copy_fishArr[f].r = nr;
			copy_fishArr[f].c = nc;
			copy_fishArr[f].dir = nd;

			copy_map[nr][nc] = f;
			copy_map[cr][cc] = -1;			//원래 물고기 있던 칸은 물고기 없어짐 

		}

	}


	//상어 이동
	for(int step = 1; step <= 3; step++) {
		int nr = shark_row + dr[shark_dir] * step;
		int nc = shark_col + dc[shark_dir] * step;

		if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4) break;

		if (copy_map[nr][nc] != -1) {
			solveDFS(copy_map, copy_fishArr, nr, nc, s);
		}
	}




}



int main() {

	int n, d;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {

			cin >> n >> d;
			Fish fish = Fish(n, d-1, i, j, true);
			map[i][j] = n;		//2차원 배열에 놓기
			fishArr[n] = fish;			//물고기 객체 배열에 넣기

		}
	}



	//상어 초기 셋팅
	ret = 0;
	solveDFS(map, fishArr, 0, 0, 0);
	cout << ret;
	
	return 0;

}

참고 블로그 : na982.tistory.com/category/%EC%82%BC%EC%84%B1%20SW%20%EC%97%AD%EB%9F%89%20%ED%85%8C%EC%8A%A4%ED%8A%B8%20%EA%B8%B0%EC%B6%9C%20%ED%92%80%EC%9D%B4?page=2