Baekjoon 16441 아기돼지와 늑대 JAVA

16441번: 아기돼지와 늑대

문제

산으로 둘러싸인 고리분지에 사는 아기돼지 삼형제는 엄마돼지로부터 독립하여 새 집을 지으려 합니다.

고리분지는 N × M 크기의 2차원 격자로 나타낼 수 있고 각 칸의 지형은 초원, 빙판, 산 중 하나입니다.

고리분지에는 돼지가족들 뿐만 아니라 늑대들도 살고 있습니다. 늑대는 상하좌우 인접한 칸 중 산이 아닌 칸으로 이동할 수 있습니다. 만약 이동한 칸이 빙판이라면 초원을 밟거나 산에 부딪칠 때까지 이동한 방향으로 미끄러집니다. 산에 부딪친 경우 늑대는 빙판 위에 가만히 서있을 수 있고 다시 다른 방향으로 이동할 수 있습니다.

게으른 아기돼지들은 지푸라기로 집을 지을 예정이기 때문에 늑대가 집이 있는 칸에 도착하기만 한다면 손쉽게 침입할 수 있습니다. 고리분지에 사는 늑대들이 도달할 수 없고 지형이 초원인 칸을 '안전한 곳'이라고 부릅니다. 게으른 아기돼지들을 위해 고리분지의 지도가 주어지면 지도 위에 모든 안전한 곳의 위치를 표시해주세요.

 

조건

[입력]

첫 번째 줄에는 격자의 행의 수를 나타내는 N (3 ≤ N ≤ 100) 과 격자의 열의 수를 나타내는 M (3 ≤ M ≤ 100) 이 주어집니다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열들이 주어집니다. 

i+1번째 줄의 j번째 문자는 i번째 행 j번째 열의 지형 종류를 의미하며 '.' 일 경우 초원, '+' 일 경우 빙판, '#' 일 경우 산, 그리고 'W'는 늑대가 살고 있음을 나타냅니다. 늑대가 사는 칸은 여러 개일 수 있고 늑대가 사는 지형은 항상 초원입니다. 지도의 첫 번째, N번째 행과 첫 번째, M번째 열은 항상 산입니다.

 

[출력]

입력으로 주어진 지도를 출력하되 아기돼지가 살 수 있는 초원은 문자 'P'로 대체하여 출력합니다.

 

풀이

해당 문제는 문제의 조건에 따라 늑대를 모두 이동시킨 후 돼지가 집을 지을 수 있는 곳을 표시해서 출력하는 문제다.

처음 문제를 보고는 그냥 늑대만 bfs 돌려주면 해결되겠다 생각하고 예외를 체크한 뒤 제출했으나 2%에서 틀렸다는 답을 받았고 생각해보니 빙판에 대해서는 방향에 따라갈 수 있는 길이 다르다는 것을 알게 되어 3차원 배열을 이용하여 방문 체크를 실시하여 해결하였다.

 

로직은 아래와 같이 구현하였다.

1. 입력 처리를 한다 이때 초원과 빙판은 방문처리를 하고, 늑대의 좌표는 큐에 담아준다.

2. bfs를 돌린다.

    1. 4방향을 탐색하는데 만약 지금 방향으로 방문을 했거나, 최초 입력값에서 방문한 경우 다음 반복문을 수행한다.

    2. 만약 초원이라면 방문 처리하고 큐에 담는다.

    3. 빙판이면 해당 방향으로 모두 체크한다.

        1. 만약 산을 만나면 한 칸 이전 좌표를 큐에 담아 주고 멈춘다.

        2. 초원을 만나면 해당 좌표를 큐에 담아 주고 멈춘다.

3. 출력한다.

    1. 3차원 방문 체크 배열중 방문한 게 없고 초원이라면 P를 출력한다.

    2. 기존 map의 값을 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N, M, dy[]={0,-1,1,0,0} , dx[]={0,0,0,-1,1};
    static char[][] map;
    static boolean[][][] visit; // 3차원으로 방문 체크
    static Queue<Wolf> queue = new LinkedList<>();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        visit = new boolean[N][M][5]; // 0은 첫번째 입력받을때 체크한곳 벽이랑 늑대

        for (int i = 0; i < N; i++) { // 입력처리
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                if(map[i][j] != '.' && map[i][j] !='+') // 초원이랑 빙판이 아니면 방문 처리
                    visit[i][j][0] = true;
                if(map[i][j] == 'W') // 늑대 좌표를 큐에 담아둔다.
                    queue.add(new Wolf(i,j));
            }
        }

        bfs();
        print();
    }

    private static void print() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!(visit[i][j][0] || visit[i][j][1] || visit[i][j][2] || visit[i][j][3] || visit[i][j][4]) && map[i][j] =='.')
                    System.out.print("P");
                else
                    System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    private static void bfs() { // bfs 돌림
        while (!queue.isEmpty()){
            Wolf wolf = queue.poll();
            for (int i = 1; i <=4; i++) {
                int ny = wolf.y + dy[i];
                int nx = wolf.x + dx[i];
                if(visit[ny][nx][i] || visit[ny][nx][0]) // 해당 방향이랑 처음 입력값 방문체크 배열 둘중 하나라도 방문하면 넘어감
                    continue;
                if(map[ny][nx] == '.'){ // 초원이면 현제 방향으로 방문처리하고 큐에담음
                    visit[ny][nx][i] = true;
                    queue.add(new Wolf(ny,nx));
                }else if(map[ny][nx] == '+'){ // 빙판이면 미끌어지기
                    while (true){
                        visit[ny][nx][i] = true; // 미끌어지면서 모두 방문체크해줌 해당 방향으로
                        ny = ny + dy[i];
                        nx = nx + dx[i];
                        if(map[ny][nx] == '#') { // 만약 산을 만나면 한칸 이전으로 이동해서 큐에 담아준다.
                            queue.add(new Wolf(ny - dy[i], nx - dx[i]));
                            break;
                        }
                        else if (map[ny][nx] == '.' || map[ny][nx] =='W') { // 초원을 만나는 경우
                            visit[ny][nx][i] = true;
                            queue.add(new Wolf(ny,nx));
                            break;
                        }
                    }
                }
            }
        }
    }

    static class Wolf{
        int y, x;
        Wolf(int y, int x){
            this.y = y;
            this.x = x;
        }
    }
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드