SWEA 1210 - Ladder1 [Java]

문제

SW Expert Academy

풀이

평범한 BFS 문제다. 단 다음 사항을 유의해야 한다.

• 이동 방향에서 x축 방향으로 위로 이동하는 것은 제외
• visited를 출발한 y좌표까지 고려해서 3차원 배열로 구성
• 하나의 방향으로 이동한 이후 나머지 방향으로의 이동은 고려하지 않음

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Solution {
	
	private static final int N = 100;
	
	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		int[] dx = {0, 0, 1};
		int[] dy = {1, -1, 0};
		
		for (int T = 0; T < 10; T++) {
			int tc = sc.nextInt();
			int[][] arr = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j] = sc.nextInt();
				}
			}
			
			int ex = N-1, ey = -1;
			for (int j = 0; j < N; j++) {
				if (arr[ex][j] == 2) {
					ey = j;
					break;
				}
			}
			
			Queue<Integer[]> queue = new LinkedList<>();
			boolean[][][] visited = new boolean[N][N][N];
			for (int j = 0; j < N; j++) {
				if (arr[0][j] == 1) {
					queue.add(new Integer[]{0, j, j});
					visited[0][j][j] = true;
				}
			}
			
			int res = -1;
			while (!queue.isEmpty()) {
				Integer[] cur = queue.poll();
				int x = cur[0], y = cur[1], s = cur[2];
				if (x == ex && y == ey) {
					res = s;
					break;
				}
				for (int i = 0; i < 3; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (isValid(nx) && isValid(ny)) {
						if (arr[nx][ny] != 0 && !visited[nx][ny][s]) {
							queue.add(new Integer[]{nx, ny, s});
							visited[nx][ny][s] = true;
							break;
						}
					}
				}
			}
			
			System.out.printf("#%d %d\n", tc, res);
		}
		
		sc.close();
	}
	
	private static boolean isValid(int x) {
		return 0 <= x && x < N;
	}
}