[백준] 3055 탈출 자바 BFS 문제 풀이 및 정답

문제 요약)

- 고슴도치 위치, 고슴도치 굴 위치, 물 위치, 돌 위치 등이 주어짐

- 고슴도치가 굴에 들어갈 수 있으면 이동거리, 없으면 주어진 문자 출력

 

주의점)

- 예외 조건이 꽤 있는 편(물이 먼저 찰 예정이면 고슴도치는 진입 불가, 물은 고슴도치 굴에 접근 불가 등)

 

풀이)

조건 중 물이 접근 예정인 곳은 고슴도치가 접근할 수 없다는 조건이 있습니다.

따라서, 물을 먼저 q에 넣고 고슴도치 위치를 별도로 저장해서 BFS돌 당시에

물이 먼저 bfs를 돌면서 위치를 선점할 수 있게하면 해당 조건을 만족 시킬 수 있습니다.

 

두 번째로, 고슴도치가 굴에 도착하는지 판단할 수 있도록 고슴도치 굴의 위치는 저장해놓고

map에서 고슴도치가 가는 길은 고슴도치로, 물이 가는 길은 물로 바꿔주면 최종적으로

저장해놨던 고슴도치 굴의 위치에 고슴도치가 들어있는지 판단해보면 알 수 있습니다.

 

정답)

java

닫기 줄바꿈

import java.util.*;

public class Escape3055_blog {
​​​​static int[] dx = {-1, 0, 1, 0};
​​​​static int[] dy = {0, 1, 0, -1};
​​​​static char[][] map;
​​​​static int[][] distance;
​​​​static int n, m;

​​​​public static void main(String[] args) {
​​​​​​​​Scanner sc = new Scanner(System.in);
​​​​​​​​n = sc.nextInt();
​​​​​​​​m = sc.nextInt();

​​​​​​​​map = new char[n][m];
​​​​​​​​distance = new int[n][m];

​​​​​​​​Queue<int[]> q1 = new LinkedList<>(); // 물만 넣어줄 q
​​​​​​​​Queue<int[]> q2 = new LinkedList<>(); // 고슴도치 넣어줄 q
​​​​​​​​int[] endPoint = new int[2]; // 고슴도치 굴 위치

​​​​​​​​for (int i=0; i<n; i++) {
​​​​​​​​​​​​String str = sc.next();

​​​​​​​​​​​​for (int j=0; j<str.length(); j++) {
​​​​​​​​​​​​​​​​char word = str.charAt(j);
​​​​​​​​​​​​​​​​map[i][j] = word;
​​​​​​​​​​​​​​​​
​​​​​​​​​​​​​​​​if (word == '*') { // 물인 경우 q1에 넣기
​​​​​​​​​​​​​​​​​​​​q1.offer(new int[] {i, j});
​​​​​​​​​​​​​​​​​​​​distance[i][j] = 1;
​​​​​​​​​​​​​​​​​​​​
​​​​​​​​​​​​​​​​} else if (word == 'S') { // 고슴도치면 q2에 넣기
​​​​​​​​​​​​​​​​​​​​q2.offer(new int[] {i, j});
​​​​​​​​​​​​​​​​​​​​distance[i][j] = 1;
​​​​​​​​​​​​​​​​​​​​
​​​​​​​​​​​​​​​​} else if (word == 'D') { // 고슴도치 굴이면 endPoint에 넣기
​​​​​​​​​​​​​​​​​​​​endPoint = new int[] {i, j};
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​BFS(q1, q2);

​​​​​​​​if (map[endPoint[0]][endPoint[1]] == 'S') {
​​​​​​​​​​​​System.out.println(distance[endPoint[0]][endPoint[1]] - 1);
​​​​​​​​} else {
​​​​​​​​​​​​System.out.println("KAKTUS");
​​​​​​​​}
​​​​}

​​​​static void BFS(Queue<int[]> q1, Queue<int[]> q2) {
​​​​​​​​Queue<int[]> q = new LinkedList<>();
​​​​​​​​while(!q1.isEmpty()) { // 반드시 물부터 넣어주기
​​​​​​​​​​​​q.offer(q1.poll());
​​​​​​​​}
​​​​​​​​while(!q2.isEmpty()) { // 고슴도치 넣기
​​​​​​​​​​​​q.offer(q2.poll());
​​​​​​​​}

​​​​​​​​while (!q.isEmpty()) {
​​​​​​​​​​​​int[] current = q.poll();
​​​​​​​​​​​​int curX = current[0];
​​​​​​​​​​​​int curY = current[1];

​​​​​​​​​​​​for (int i=0; i<dx.length; i++) {
​​​​​​​​​​​​​​​​int nx = curX + dx[i];
​​​​​​​​​​​​​​​​int ny = curY + dy[i];

​​​​​​​​​​​​​​​​// index에러 방지, 문제에서 주어진 조건 넣기
​​​​​​​​​​​​​​​​if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
​​​​​​​​​​​​​​​​if (distance[nx][ny] > 0 || map[nx][ny] == 'X' || distance[nx][ny] == 'S' || distance[nx][ny] == '*') continue;
​​​​​​​​​​​​​​​​if (map[curX][curY] == '*' && map[nx][ny] == 'D') continue;

​​​​​​​​​​​​​​​​// 제외할 조건 외에는 q에 넣어서 진행
​​​​​​​​​​​​​​​​q.offer(new int[] {nx, ny});
​​​​​​​​​​​​​​​​distance[nx][ny] = distance[curX][curY] + 1;
​​​​​​​​​​​​​​​​map[nx][ny] = map[curX][curY];
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}
}