[BOJ] 소년점프 16469.java

 문제

www.acmicpc.net/problem/16469

굉장히 괜찮았던 문제이다. 어려운 문제는 아니었는데, 접근하는 방법을 조금 다르게 생각해봐야하는 좋은 문제였다.

-  첫 줄에 주어진 R, C로 만들어진 map

- q1, q2, q3 3명이 동시에 한 지점에 도착할 때의 최단 시간을 찾으면 된다.

 

 해설 및 코드

코드 자체는 어렵지 않게 풀어서, 큰 주석을 붙이지는 않았다.

BFS로 문제를 풀었는데, Deepening을 사용해서 한 번에 이동이 가능한 size만큼 체크를 해줬다.

어디든 갈 수 있기 때문에, 방문 할 수 있으면 무조건 True로 만들어줬다.

이후, 전체 map을 탐색해서 세 check 배열이 모두 True인 구간이 있으면 개수를 센 후에 종료해줬다. 최단만 찾으면 되니까!

package 백준;

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

public class 소년점프_16469 {
	static class Node {
		int r;
		int c;

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

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int R = sc.nextInt();
		int C = sc.nextInt();

		int[][] map = new int[R + 1][C + 1];

		for (int i = 1; i <= R; i++) {
			String st = sc.next();
			for (int j = 0; j < C; j++) {
				map[i][j + 1] = st.charAt(j) - '0';
			}
		}

		Queue<Node> q1 = new LinkedList<>();
		Queue<Node> q2 = new LinkedList<>();
		Queue<Node> q3 = new LinkedList<>();
		
		boolean[][] ck1 = new boolean[R + 1][C + 1];
		boolean[][] ck2 = new boolean[R + 1][C + 1];
		boolean[][] ck3 = new boolean[R + 1][C + 1];
		

		int a = sc.nextInt();
		int b = sc.nextInt();

		q1.add(new Node(a, b));
		ck1[a][b] = true;

		a = sc.nextInt();
		b = sc.nextInt();
		q2.add(new Node(a, b));
		ck2[a][b] = true;

		
		a = sc.nextInt();
		b = sc.nextInt();
		q3.add(new Node(a, b));
		ck3[a][b] = true;


		int[] dr = { 0, 0, 1, -1 };
		int[] dc = { 1, -1, 0, 0 };

		

		int cnt = 0;
		while (!q1.isEmpty() && !q2.isEmpty() && !q3.isEmpty()) {
			cnt++;

			int s1 = q1.size();
			int s2 = q2.size();
			int s3 = q3.size();

			for (int i = 0; i < s1; i++) {
				Node b1 = q1.poll();
				for (int d = 0; d < 4; d++) {
					int r1 = b1.r + dr[d];
					int c1 = b1.c + dc[d];
					if (r1 <= 0 || c1 <= 0 || r1 > R || c1 > C || map[r1][c1] == 1 || ck1[r1][c1]) {
					} else {
						q1.add(new Node(r1, c1));
						ck1[r1][c1] = true;
					}
				}
			}

			for (int i = 0; i < s2; i++) {
				Node b2 = q2.poll();
				for (int d = 0; d < 4; d++) {
					int r2 = b2.r + dr[d];
					int c2 = b2.c + dc[d];
					if (r2 <= 0 || c2 <= 0 || r2 > R || c2 > C || map[r2][c2] == 1 || ck2[r2][c2]) {
					} else {
						ck2[r2][c2] = true;
						q2.add(new Node(r2, c2));
					}
				}
			}

			for (int i = 0; i < s3; i++) {
				Node b3 = q3.poll();
				for (int d = 0; d < 4; d++) {
					int r3 = b3.r + dr[d];
					int c3 = b3.c + dc[d];
					if (r3 <= 0 || c3 <= 0 || r3 > R || c3 > C || map[r3][c3] == 1 || ck3[r3][c3]) {
					} else {
						ck3[r3][c3] = true;
						q3.add(new Node(r3, c3));
					}
				}
			}

			int rs = 0;

			for (int i = 1; i <= R; i++) {
				for (int j = 1; j <= C; j++) {
					if (ck1[i][j] && ck2[i][j] && ck3[i][j]) {
						rs++;
					}
				}
			}

			if (rs != 0) {
				System.out.println(cnt);
				System.out.println(rs);
				return;
			}
		}

		System.out.println(-1);
	}
}

- Queue에 처음 값을 넣고 check 배열을 True로 만들어 주는 것을 까먹어서 계속 100%에서 오류가 났었다.