백준:탈출-3055

---

package dfs.Day250305;

import java.io.*;
import java.util.*;

public class Day02_탈출 {
    public static int r;
    public static int c;
    public static char[][] table;
    public static int result = -1;
    public static Queue<Node> water;
    public static Queue<Node> animal;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

    public static class Node {
        int x;
        int y;
        int minute;

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

    public static void bfs() {

        while (!animal.isEmpty()) {

            // 물 먼저
            int waterLen = water.size();
            for (int i = 0; i < waterLen; i++) {
                Node waterNode = water.poll();

                for (int j = 0; j < 4; j++) {
                    int x = dx[j] + waterNode.x;
                    int y = dy[j] + waterNode.y;

                    if (x >= 0 && y >= 0 && x < c && y < r && (table[y][x] == '.')) {
                        table[y][x] = '*';
                        water.add(new Node(x, y, waterNode.minute + 1));
                    }
                }
            }

            int animalLen = animal.size();
            for (int i = 0; i < animalLen; i++) {
                Node animalNode = animal.poll();

                for (int j = 0; j < 4; j++) {
                    int x = dx[j] + animalNode.x;
                    int y = dy[j] + animalNode.y;

                    if (x >= 0 && y >= 0 && x < c && y < r) {
                        if (table[y][x] == 'D') {
                            result = animalNode.minute;
                            return;
                        } else if (table[y][x] == '.') {
                            table[y][x] = 'S';
                            animal.add(new Node(x, y, animalNode.minute + 1));
                        }
                    }
                }
            }


        }


    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());// 세로
        c = Integer.parseInt(st.nextToken());// 가로

        table = new char[r][c];
        water = new ArrayDeque<>();
        animal = new ArrayDeque<>();

        for (int i = 0; i < r; i++) {
            String s = br.readLine();
            for (int j = 0; j < c; j++) {
                char c = s.charAt(j);
                table[i][j] = c;

                if (c == '*') {
                    water.add(new Node(j, i, 1));
                }

                if (c == 'S') {
                    animal.add(new Node(j, i, 1));
                }
            }
        }

        bfs();
        if (result == -1) {
            System.out.println("KAKTUS");
        }
        else {
            System.out.println(result);
        }
    }

}

문제

오늘은 탈출이라는 문제를 풀었습니다.

문제를 요약하면 홍수가 났고 고슴도치는 비버가 지어놓은 집으로 도망가야 됩니다.
그런데 1분마다 고슴도치는 한칸씩 이동이 가능합니다.
그런데 1분마다 물이 찹니다.

그러면 고슴도치는 물에 닿이지 않고 비버집에 도착하는 최소 거리를 구하면 됩니다.

3 3
D.*
...
.S.

D - 비버 집
. - 땅
S - 고슴도치

그러면 물이랑 고슴도치가 동시에 움직여야 합니다.
동시에 움직이는 것이면 bfs를 써야 합니다.

설명

for (int i = 0; i < r; i++) {
	String s = br.readLine();
    for (int j = 0; j < c; j++) {
    	char c = s.charAt(j);
	    table[i][j] = c;

		if (c == '*') {
			water.add(new Node(j, i, 1));
		}

		if (c == 'S') {
			animal.add(new Node(j, i, 1));
		}
	}
}

그러면 물이 차있는 곳과 고슴도치가 있는 곳을 미리 큐에 넣습니다.

• BFS

while (!animal.isEmpty()) {

	// 물 먼저
	int waterLen = water.size();
		for (int i = 0; i < waterLen; i++) {
			Node waterNode = water.poll();

			for (int j = 0; j < 4; j++) {
				int x = dx[j] + waterNode.x;
				int y = dy[j] + waterNode.y;

				if (x >= 0 && y >= 0 && x < c && y < r && (table[y][x] == '.')) {
                        table[y][x] = '*';
                        water.add(new Node(x, y, waterNode.minute + 1));
				}
			}
		}

		int animalLen = animal.size();
		for (int i = 0; i < animalLen; i++) {
			Node animalNode = animal.poll();

			for (int j = 0; j < 4; j++) {
				int x = dx[j] + animalNode.x;
				int y = dy[j] + animalNode.y;

				if (x >= 0 && y >= 0 && x < c && y < r) {
					if (table[y][x] == 'D') {
						result = animalNode.minute;
						return;
					} else if (table[y][x] == '.') {
						table[y][x] = 'S';
						animal.add(new Node(x, y, animalNode.minute + 1));
					}
				}
			}
		}
	}
}

고슴도치 기준으로 돌아갑니다. 고슴도치가 큐에 없으면 종료가 됩니니다.

for (int i = 0; i < waterLen; i++) {
	Node waterNode = water.poll();

	for (int j = 0; j < 4; j++) {
		int x = dx[j] + waterNode.x;
		int y = dy[j] + waterNode.y;

		if (x >= 0 && y >= 0 && x < c && y < r && (table[y][x] == '.')) {
			table[y][x] = '*';
			water.add(new Node(x, y, waterNode.minute + 1));
		}
	}
}

밖에 있는 for문은 먼저 홍수가 난 땅이 두 군데 이상 일 경우 그 만큼 물이 퍼지도록 합니다.

int animalLen = animal.size();
for (int i = 0; i < animalLen; i++) {
	Node animalNode = animal.poll();

	for (int j = 0; j < 4; j++) {
		int x = dx[j] + animalNode.x;
		int y = dy[j] + animalNode.y;

		if (x >= 0 && y >= 0 && x < c && y < r) {
			if (table[y][x] == 'D') {
				result = animalNode.minute;
				return;
			} else if (table[y][x] == '.') {
				table[y][x] = 'S';
				animal.add(new Node(x, y, animalNode.minute + 1));
			}
		}
	}
}

그리고 고슴도치가 갈수 있는 경우 수 만큼 퍼집니다.

홍수는 고슴도치를 덮을 수 있기 때문에 갈 수 있는 경우의 수를 가도 됩니다.
어차피 홍수가 덮다가 고슴도치가 도착지에 도착하면 if문에서 걸리고 아니면 다 덮어버리면 고슴도치가 도착할수 없는 경우의 수 가 나온겁니다.

위에서 설명 했듯이

if (x >= 0 && y >= 0 && x < c && y < r) {
	if (table[y][x] == 'D') {
		result = animalNode.minute;
		return;
	} else if (table[y][x] == '.') {
		table[y][x] = 'S';
		animal.add(new Node(x, y, animalNode.minute + 1));
	}
}

고슴도치가 돌다가 도착지에 도착하면 결과 값을 대입합니다.
아니면 S를 넣어서 갈 수 있는 경우의 수를 갑니다.

자잘 한 실수들

문제를 푸는데 한 시간 이상 쓴거 같습니다.
큰 실수가 두가지 있었습니다.

1. for (int i = 0; i < water.size(); i++)
   조건문에 water.size()를 쓴것 처음에 이제 물이 난 곳은 1곳인데 두번 씩이나 돌아가길레 뭔가 싶어서 디버그를 돌리고 나서 알았는데 생각해보니 water.add(...)이 되면 water.size()가 켜저서 반목문이 한번 더 돌아간다.

2. D를 찾았을 때 바로 return을 안함
   이제 목적지에 도착했을때 bfs에서 탈출을 안 하니 문제가 틀렸다고 떳습니다. 거의 이부분에서 한시간 쓴거 같습니다.