[Softeer]나무 섭지

https://softeer.ai/practice/7726

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

남우가 출구를 향해 가는데,

가는길에 벽이라는 장애물이 있을 수 있고, 유령을 만나면 안된다.

유령은 벽을 통과할 수 있다.

출구에 도달하는 순간 유령을 만나도 안된다.

 

위 조건을 만족하여 남우가 출구에 도달할 수 있을까?

 

남우가 움직이는 칸이 유령이 있을 수 있는지 확인하기 위해서

Queue 에 데이터를 담을때, 유령을 먼저 담고 남우의 위치를 나중에 담았다.

 

그리고 유령이 지나간 위치와, 남우가 지나간 위치를 구분하기 위해서 boolean[][][] pass를 선언하고, 

1차원 배열은 i위치, 2차원 배열은 j위치, 그리고  3차원 배열은 유령[1]인지 남우[0]인지 확인하는 변수를 담아

BFS(Breadth-First Search), 즉 너비우선탐색을 하여 남우가 갈수 있는 길을 점점 확장했다.

 

그렇게 해서 남우가 출구까지 무사히 도달 했으면 "Yes", 도달하지 못했으면 "No".

 

이정도 난이도의 BFS 문제라면 언제든 환영이다...

 

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

public class Main {

    static class Pair{
        int x, y;
        boolean ghost;
        Pair(int x, int y, boolean ghost){
            this.x = x;
            this.y = y;
            this.ghost = ghost;
        }
    }

    static int[] dx = {-1,0,0,1};
    static int[] dy = {0,-1,1,0};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        char[][] a = new char[n][m];
        Pair n_location = null;
        Queue<Pair> q = new LinkedList<>();
        boolean[][][] pass = new boolean[n][m][2];
        for(int i=0; i<n; i++){
            a[i] = br.readLine().toCharArray();
            for(int j=0; j<m; j++){
                if(a[i][j] == 'G'){
                    q.add(new Pair(i, j, true));
                    pass[i][j][1] = true;
                }else if(a[i][j] == 'N'){
                    n_location = new Pair(i, j, false);
                    pass[i][j][0] = true;
                }
            }
        }
        q.add(n_location);
        String ans = "No";
        while(!q.isEmpty()){
            Pair p = q.poll();
            int x = p.x;
            int y = p.y;
            boolean ghost = p.ghost;
            for(int k=0; k<4; k++){
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(ghost){
                    if(pass[nx][ny][1]) continue;
                    pass[nx][ny][1] = true;
                    q.add(new Pair(nx, ny, true));
                }else{
                    if(a[nx][ny] == '#' || pass[nx][ny][0] || pass[nx][ny][1]) continue;
                    if(a[nx][ny] == '.'){
                        pass[nx][ny][0] = true;
                        q.add(new Pair(nx, ny, false));
                    }else if(a[nx][ny] == 'D'){
                        ans = "Yes";
                        q.clear();
                        break;
                    }
                }
            }
        }
        bw.write(ans);
        bw.close();
    }
}