[Baekjoon]17070.파이프 옮기기1

17070.파이프 옮기기1

http://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

---

문제를 읽어보니 바로 전에 풀었던 SWEA의 탈주범검거 문제와  비슷하다는 느낌을 받았다. 일단 현재 파이프가 놓인 상태에 따라서 다음에 파이프가 놓여질 수 있는 상태가 다르다는 점때문에 모든 방향으로 탐색을 계속하지 않고 조건에 따라서 탐색방향을 정하는 것이 탈주범 검거 문제의 조건과 비슷하다고 생각했다.  따라서 탐색할 때 매개변수로 현재 파이프의 상태를 저장할 con변수를 사용했다. 

 

탈주범 검거 문제와 다르게 이 문제는 도착지에 도착하는 경우의 수를 구해야 하므로  dfs를 사용했다. 파이프가 두칸을 차지하게 되는데 어차피 파이프 앞부분이 이동하면 뒷부분은 앞부분이 있던 자리로 따라오기 때문에 파이프 앞부분만 신경쓰면 된다. 따라서 dfs시작도 (0,0)이 아닌 파이프 앞부분이 위치한(1,0)에서 시작한다. 

 

탐색 방향의 조건은 다음과 같다.

만약에 현재 파이프가 세로로 놓여 있다면 다음에는 세로 또는 대각선으로만 놓여질 수 있다. 

가로로 놓여있다면 다음에는 가로 또는 대각선, 대각선으로 놓여있다면 모두 가능하다.

 

• 가로 방향으로 탐색이 가능한 경우는 현재 파이프가 가로로 놓여져 있거나 대각선으로 놓여진 경우
• 세로 방향으로 탐색이 가능한 경우는 현재 파이프가 세로로 놓여져 있거나 대각선으로 놓여진경우
• 대각선 방향으로 탐색이 가능한 경우는 현재 파이프가 어떻게 놓여져 있건 상관없다.

if (i == 0) { // 가로방향
	if (curCon == 0 || curCon == 2) {
		dfs(nextX, nextY, 0);
	}
}
if (i == 1) { // 세로방향
	if (curCon == 1 || curCon == 2) {
		dfs(nextX, nextY, 1);
	}
}
if (i == 2 && checkAround(curX, curY)) { // 대각방향
	dfs(nextX, nextY, 2);
}

그런데 마지막에 대각선 방향으로 탐색할 때 주의할 점은 대각선 이동을 하려면 현재 파이프 지점의 주변이 모두 벽이 없어야 가능하다는 점이다. 이것을 처리하기 위해 checkAround함수를 만들어 비어있으면 대각선이동을 하고 벽이 하나라도 있으면 대각선이동을 못하게 한다.

private static boolean checkAround(int x, int y) {

		for (int i = 0; i < 3; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			if (map[nextY][nextX] == 1) {
				return false;
			}
		}
		return true;
	}

 

<전체코드>