[알고리즘] 파이프 옮기기 1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	static int[][] map;
	static int[][] dp;
	static int[][] dir;
	static int[][] dr;
	static int[][] dc;
	static int N;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dp = new int[N][N];
		dr = new int[][] {{0, 1}, {0, 1, 1}, {0, 1, 1}};
		dc = new int[][] {{1, 1}, {1, 1, 0}, {0, 1, 0}};
		
		bfs(new int[] {0, 1, 0});
		System.out.println(dp[N-1][N-1]);
	}

	// point : {r, c, dir}
	private static void bfs(int[] point) {
		Deque<int[]> deque = new ArrayDeque<>();
		deque.add(point);
		while(!deque.isEmpty()) {
			point = deque.poll();
			int r = point[0];
			int c = point[1];
			int dir = point[2];
			for (int i = 0; i < dr[dir].length; i++) {
				if (dr[dir][i] == 0 && dc[dir][i] == 0) {
					continue;
				}
				int nr = r + dr[dir][i];
				int nc = c + dc[dir][i];
		
				if (0 <= nr && nr < N && 0 <= nc && nc < N && map[nr][nc] != 1) {
					if (i == 1) {
						if (map[nr-1][nc] == 1 || map[nr][nc-1] == 1) {
							continue;
						}
					}
					dp[nr][nc] += 1;
					deque.add(new int[] {nr, nc, i});
				}
			}
		}
	}
}

- bfs로 풀어도 풀린다.

- dp로도 풀 수 있다.