BOJ 17070. 파이프 옮기기 1

DP - for loop
DP - recursive & memoization
BFS

DP - for loop

dp[i][j][k] : k 방향으로 파이프를 두어 (i, j)에 도달 했을 떄의 경우의 수
- k : 0(VERTICAL), 1(HORIZONTAL), 2(DIAGONAL)
방향에 따라 이전(previous) 단계에서 넘어올 수 있는 방향의 종류 및 수가 달라진다.
- VERTICAL : 이전의 VERTICAL, DIAGONAL
- HORIZONTAL : 이전의 HORIZONTAL, DIAGONAL
- DIAGONAL : 이전의 VERTICAL, HORIZONTAL, DIAGONAL
대각선의 경우 현재 좌표의 상대 좌표 (-1, -1), (-1, 0), (0, -1)이 모두 벽이 아니어야 가능하다
dp[1][2][1]을 1로 초기 설정해주어야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define MAX_N 20
#define WALL 1

#define VERTICAL 0
#define HORIZONTAL 1
#define DIAGONAL 2

int N;
int board[MAX_N][MAX_N];
// dp[i][j][k] : k 방향으로 파이프를 두어 (i, j)에 도달 했을 떄의 경우의 수
int dp[MAX_N][MAX_N][3];

void solution() {
	dp[1][2][1] = 1;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (board[i][j] == WALL) continue;

			if (board[i-1][j] != WALL)
				dp[i][j][0] += (dp[i-1][j][0] + dp[i-1][j][2]);
			if (board[i][j-1] != WALL)
				dp[i][j][1] += (dp[i][j-1][1] + dp[i][j-1][2]);
			if (board[i-1][j-1] != WALL && board[i][j-1] != WALL && board[i-1][j] != WALL)
				dp[i][j][2] += (dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]);
		}
	}
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			scanf("%d", &board[i][j]);

	solution();
	int res = 0;
	for (int i = 0; i < 3; i++)
		res += dp[N][N][i];

	printf("%d\n", res);
}

DP - recursive & memoization

memo[i][j][k] : k 방향으로 파이프를 두어 (i, j)에 도달 했을 떄의 경우의 수
- k : 0(VERTICAL), 1(HORIZONTAL), 2(DIAGONAL)
방향에 따라 이전(previous) 단계에서 넘어올 수 있는 방향의 종류 및 수가 달라진다.
- VERTICAL : 이전의 VERTICAL, DIAGONAL
- HORIZONTAL : 이전의 HORIZONTAL, DIAGONAL
- DIAGONAL : 이전의 VERTICAL, HORIZONTAL, DIAGONAL
대각선의 경우 현재 좌표의 상대 좌표 (-1, -1), (-1, 0), (0, -1)이 모두 벽이 아니어야 가능하다
dp[1][2][1]을 1로 초기 설정해주어야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int[][] board;
	// memo[i][j][k] : k 방향으로 파이프를 두어 (i, j)에 도달 했을 떄의 경우의 수
	static int[][][] memo; 

	static final int WALL = 1;

	static final int VERTICAL = 0;
	static final int HORIZONTAL = 1;
	static final int DIAGONAL = 2;

	
	static int go(int r, int c, int s) {
		if \(r < 1 \|| r > N \|| c < 1 \|| c > N \|| board\[r]\[c] == WALL)
			return 0;

		if (memo[r][c][s] != -1) return memo[r][c][s];
		memo[r][c][s] = 0;

		if (s == VERTICAL) {
			if (r-1 >= 1 && board[r-1][c] != WALL) {
				memo[r][c][s] += go(r-1, c, VERTICAL);
				memo[r][c][s] += go(r-1, c, DIAGONAL);
			}
		} else if (s == HORIZONTAL) {
			if (c-1 >= 1 && board[r][c-1] != WALL) {
				memo[r][c][s] += go(r, c-1, HORIZONTAL);
				memo[r][c][s] += go(r, c-1, DIAGONAL);
			}
		} else {
			if (r-1 >=1 && c-1 >=1 && board[r-1][c] != WALL && board[r][c-1] != WALL) {
				memo[r][c][s] += go(r-1, c-1, VERTICAL);
				memo[r][c][s] += go(r-1, c-1, HORIZONTAL);
				memo[r][c][s] += go(r-1, c-1, DIAGONAL);
			}
		}
		return memo[r][c][s];
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine());
		board = new int[N+1][N+1];
		memo = new int[N+1][N+1][3];
		for (int[][] d2 : memo) for (int[] d1 : d2) Arrays.fill(d1, -1);

		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			for (int j = 1; j <= N; j++)
				board[i][j] = Integer.parseInt(st.nextToken());
		}
		memo[1][2][HORIZONTAL] = 1;

		int res = 0;
		for (int s = 0; s < 3; s++) res += go(N, N, s);
		System.out.println(res);
	}
}

BFS

r, c, dir를 갖는 Node class 생성
queue에서 pop한 Node의 방향에 따라 다음에 갈 수 있는 방향의 종류 및 수가 달라진다.
- VERTICAL -> VERTICAL, DIAGONAL
- HORIZONTAL -> HORIZONTAL, DIAGONAL
- DIAGONAL -> VERTICAL, HORIZONTAL, DIAGONAL
대각선의 경우 현재 위치의 상대 좌표 (1, 1), (1, 0), (0, 1)이 모두 벽이 아니어야 가능하다
시작점은 (1, 2), HORINONATAL이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

import java.io.*;
import java.util.*;

public class Main {
	static final int WALL = 1;
	static int N;
	static int[][] board;

	static final int VERTICAL = 0;
	static final int HORIZONTAL = 1;
	static final int DIAGONAL = 2;

	static class Node {
		int r, c, dir;
		Node (int r, int c, int dir) {
			this.r = r;
			this.c = c;
			this.dir = dir;
		}
	}

	static int bfs() {
		int res = 0;
		Queue<Node> q = new ArrayDeque<>();
		q.offer(new Node(1, 2, HORIZONTAL));
		while (!q.isEmpty()) {
			Node cur = q.poll();
			if (cur.r == N && cur.c == N) {
				res++;
				continue;
			}
			int nr = 0, nc = 0;
			if \(cur.dir == HORIZONTAL \|| cur.dir == DIAGONAL) {
				nr = cur.r;
				nc = cur.c + 1;
				if (0 < nr && nr <= N && 0 < nc && nc <= N && board[nr][nc] != WALL)
					q.offer(new Node(nr, nc, HORIZONTAL));
			}
			if \(cur.dir == VERTICAL \|| cur.dir == DIAGONAL) {
				nr = cur.r + 1;
				nc = cur.c;
				if (0 < nr && nr <= N && 0 < nc && nc <= N && board[nr][nc] != WALL)
					q.offer(new Node(nr, nc, VERTICAL));
			}
			nr = cur.r + 1;
			nc = cur.c + 1;
			if (0 < nr && nr <= N && 0 < nc && nc <= N
					&& board[nr][nc] != WALL && board[nr-1][nc] != WALL && board[nr][nc-1] != WALL)
				q.offer(new Node(nr, nc, DIAGONAL));
		}
		return res;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine());
		board = new int[N+1][N+1];
		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			for (int j = 1; j <= N; j++)
				board[i][j] = Integer.parseInt(st.nextToken());
		}
		System.out.println(bfs());
	}
}