✨ 문제

백준 17070 파이프 옮기기1

🎈 접근 방식

1. (1, 2) 좌표부터 시작해서 시작은 오른쪽을 향한다. 향하고 있는 방향에 따라 회전할 수 있는 경우가 다르기에 x좌표, y좌표, 바라보는 방향을 클래스로 생성하여 큐에 넣어준다.
2. 큐에서 현재 좌표를 꺼내어서 회전할 수 있는지를 체크하고 회전시킬 수 있다면 큐에 넣어준다.
3. 반복해나가면서 (N, N)까지 도착하는 방법들을 세어야 하니깐 큐에서 꺼내줄 때마다 (N, N)과 일치하는지 확인하고 일치한다면 cnt++를 해주고 while문을 continue한다.

이 문제에서 가로 방향과 세로 방향은 체크를 해줄 때 범위 내에 존재하는지 확인하고 이동하려는 좌표값이 1이 아니어야 한다. 벽을 만나면 안되기 때문이다. 따라서, 2가지를 체크해주는데 대각선으로 이동하려면 대각선 방향이 범위내에 존재하는지 확인하고 나머지 2개의 좌표값도 1이 아니어야 이동이 가능하다!!

😫 실수한 점이나 놓친 점

처음에 그냥 하드코딩으로 엄청 길게 코드를 작성해나갔다.. 일단은 시간초과가 겨우 안뜨고 통과가 되었는데 조금 더 시간을 줄일 수 있는 부분이 있을까 싶어서 찾아보았더니 while문을 돌 때 큐에서 꺼낸 후, 행이 만약 마지막 행에 도달하였고 방향이 아래방향일 때는 이동이 불가능하기 때문에 continue를 시켜준다.
마찬가지로, 꺼낸 좌표가 마지막 열에 도달하였고 방향이 가로 방향이라면 이동이 불가능하기에 continue를 시켜줌!! 이렇게 해주니깐 처음 작성한 코드보다 조금 더 시간이 줄어들었다 !!
이런 문제에서는 좌표값 설정을 할 때나 인덱스를 사용할때 실수가 없도록 더 조심해야 할 거 같다!

💻 풀이 코드

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

public class Main {
	static int N, cnt;
	static int[][] map;

	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 + 1][N + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// 마지막 지점이 1(벽)인 경우 바로 0으로 처리를 시켜준다면 시간초과 통과
		if (map[N][N] == 1) {
			System.out.println(0);
		} else {
			bfs(1, 2, 0);
			System.out.println(cnt);
		}

	}

	static void bfs(int x, int y, int d) {
		Queue<Node> queue = new ArrayDeque<>();
		queue.offer(new Node(x, y, d));

		while (!queue.isEmpty()) {
			Node node = queue.poll();
			int nowX = node.x;
			int nowY = node.y;
			int nd = node.d;

			if (nowX == N && nowY == N) {
				cnt++;
				continue;
			} else if (nowX == N && nd == 2) {
				continue;
			} else if (nowY == N && nd == 0) {
				continue;
			}
			// 현재 가로 파이프라면 다음으로는 가로 혹은 대각으로만 이동 가능
			if (nd == 0) {
				if (isValid(node, 0)) {
					queue.offer(new Node(nowX, nowY + 1, 0));
				}
				if (isValid(node, 1)) {
					queue.offer(new Node(nowX + 1, nowY + 1, 1));
				}
			} else if (nd == 1) {
				if (isValid(node, 0)) {
					queue.offer(new Node(nowX, nowY + 1, 0));
				}
				if (isValid(node, 1)) {
					queue.offer(new Node(nowX + 1, nowY + 1, 1));
				}
				if (isValid(node, 2)) {
					queue.offer(new Node(nowX + 1, nowY, 2));
				}
			} else if (nd == 2) {
				if (isValid(node, 1)) {
					queue.offer(new Node(nowX + 1, nowY + 1, 1));
				}
				if (isValid(node, 2)) {
					queue.offer(new Node(nowX + 1, nowY, 2));
				}
			}

		}
	}

	static boolean isValid(Node node, int now) {
		if (now == 0) {
			if (node.y + 1 <= N && map[node.x][node.y + 1] != 1) {
				return true;
			}
		} else if (now == 1) {
			if (node.x + 1 <= N && node.y + 1 <= N && map[node.x + 1][node.y + 1] != 1 && map[node.x][node.y + 1] != 1
					&& map[node.x + 1][node.y] != 1) {
				return true;
			}
		} else if (now == 2) {
			if (node.x + 1 <= N && map[node.x + 1][node.y] != 1) {
				return true;
			}
		}
		return false;
	}

	static class Node {
		int x, y, d; // d는 해당 좌표가 가로, 대각 ,세로 중 어떤 것인지

		public Node(int x, int y, int d) {
			this.x = x;
			this.y = y;
			this.d = d;
		}

	}
}