백준 17070번 <파이프 옮기기1>

백준 알고리즘 17070번

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

17070번: 파이프 옮기기 1

---

17070번

N*N 격자가 있고 2개의 연속된 칸을 차지하는 크기의 파이프가 존재할 때, (1, 1), (1, 2) 위치에 가로로 놓여져 있는 파이프를 한쪽 끝이 (N, N)으로 갈 수 있는 이동 방법의 수를 구하여라.

파이프는 항상 빈 칸만 차지해야 하며, 파이프를 밀 수 있는 방향은 총 3가지 →, ↓, ↘ 방향이다. 또한 회전을 45도만 회전 시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

 

입력으로 격자의 크기 N이 들어오고 그 다음 N개의 줄에 걸쳐 격자의 상태가 들어온다. 

0일 때는 빈 칸, 1일 때는 벽을 의미한다.

---

문제 해결

문제에서 주어진 정보를 보면 파이프가 가로로 놓여져 있을 땐 가로, 대각선 방향으로 움직일 수 있고, 세로로 놓여져 있을 땐 세로, 대각선 방향으로, 대각선으로 놓여져 있을 땐 가로, 세로, 대각선 방향으로 움직일 수 있다.

 

파이프의 현재 위치를 분홍색으로 표현하였고 각각 움직일 수 있는 곳으로 움직였을 때의 위치를 보라색으로 표현하였다. 

대각선의 경우, 가로와 세로보다 2개의 칸을 더 차지하기 때문에 이는 연한 색으로 표현하였다.

• 가로

• 세로

• 대각선

3개의 그림에서 규칙을 찾을 수 있다.

• 파이프의 현재 위치의 오른쪽 위치가 움직인 후에는 왼쪽 위치가 된다.
• 움직인 후의 오른쪽 위치는 움직인 후의 왼쪽 위치의 행에 +1을 하거나 안하거나, 열에 +1을 하거나 안하거나 이다.

 

격자의 크기인 N이 최대 16까지이기 때문에 이 2개의 규칙을 이용해 완전 탐색으로 풀이를 하였다.

 

먼저 격자의 상태를 boolean형 2차원 배열 Map에 저장하였는데 빈 칸일 경우 이동할 수 있으므로 true, 벽의 경우 이동할 수 없으므로 false로 하였다. 

또한 파이프의 위치를 표현하기 위해 Tuple이라는 클래스를 구현하여 사용하였고 파이프가 놓여있는 방향을 가로는 0, 세로는 1, 대각선은 2로 표현하였다.

+ 문제는 1-index 였지만 0-index로 바꿔서 코드를 구현하였다.

 

재귀 함수 move를 이용하여 완전 탐색을 하였다. 

 

move 함수는 인자로 파이프의 왼쪽 위치 a와 오른쪽 위치 b, 현재 파이프가 놓여있는 방향 d를 받는다.

기저 조건은 b가 (N-1, N-1) 일 때로, 그런 경우를 count 하였다.

1. d가 0인 경우
   1. 가로 방향으로 움직일 수 없다면 return한다. (가로 방향으로 움직일 수 없다면, 대각선 방향으로도 움직일 수 없기 때문에 return 해도 문제가 되지 않는다.)
   2. 가로 방향으로 움직이기 위해 move 함수를 호출한다.
   3. 대각선 방향으로 움직일 수 있는지 확인한다. 이때, b 위치의 아래, 오른쪽 대각선 아래 2가지 위치를 확인해야 한다. 움직일 수 없다면 return 한다. (b 위치의 오른쪽도 확인해야 하지만 해당 위치로 갈 수 없다면 이미 1번에서 return 되었을 것이기 때문에 확인하지 않았다.)
   4. 대각선 방향으로 움직이기 위해 move 함수를 호출한다.
2. d가 1인 경우
   1. 세로 방향으로 움직일 수 없다면 return한다. (세로 방향으로 움직일 수 없다면, 대각선 방향으로도 움직일 수 없기 때문에 return 해도 문제가 되지 않는다.)
   2. 세로 방향으로 움직이기 위해 move 함수를 호출한다.
   3. 대각선 방향으로 움직일 수 있는지 확인한다. 이때, b 위치의 오른쪽 대각선 아래, 오른쪽 2가지 위치를 확인해야 한다. 움직일 수 없다면 return 한다. (b 위치의 아래쪽도 확인해야 하지만 해당 위치로 갈 수 없다면 이미 1번에서 return 되었을 것이기 때문에 확인하지 않았다.)
   4. 대각선 방향으로 움직이기 위해 move 함수를 호출한다.
3. d가 2인 경우
   1. 가로 방향으로 움직일 수 있다면 move 함수를 호출한다.
   2. 세로 방향으로 움직일 수 있다면 move함수를 호출한다.
   3. 대각선 방향으로 움직일 수 있다면 move 함수를 호출한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static int N, ans;
	static boolean[][] Map;

	static class Tuple {
		int i, j;

		public Tuple(int i, int j) {
			super();
			this.i = i;
			this.j = j;
		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		Map = new boolean[N][N];
		ans = 0;
		for (int i = 0; i < N; i++) {
			String[] inArr = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				if (inArr[j].equals("0")) {
					Map[i][j] = true;
				}
			}
		}
		move(new Tuple(0, 0), new Tuple(0, 1), 0);
		System.out.println(ans);
	}

	public static void move(Tuple a, Tuple b, int d) {
		if (b.i == N - 1 && b.j == N - 1) {
			ans++;
			return;
		}
		int ni = b.i + 1;
		int nj = b.j + 1;
		if (d == 0) {
			if (nj >= N || !Map[b.i][nj]) {
				return;
			}
			move(b, new Tuple(b.i, nj), 0);
			if (ni >= N || !Map[ni][b.j] || !Map[ni][nj]) {
				return;
			}
			move(b, new Tuple(ni, nj), 2);
		} else if (d == 1) {
			if (ni >= N || !Map[ni][b.j]) {
				return;
			}
			move(b, new Tuple(ni, b.j), 1);
			if (nj >= N || !Map[b.i][nj] || !Map[ni][nj]) {
				return;
			}
			move(b, new Tuple(ni, nj), 2);
		} else if (d == 2) {
			if (0 <= nj && nj < N && Map[b.i][nj]) {
				move(b, new Tuple(b.i, nj), 0);
			}
			if (ni < N && Map[ni][b.j]) {
				move(b, new Tuple(ni, b.j), 1);
			}
			if (ni >= N || nj >= N || !Map[b.i][nj] || !Map[ni][b.j] || !Map[ni][nj]) {
				return;
			}
			move(b, new Tuple(ni, nj), 2);
		}
	}

}

 

---

결과

 

---