[softeer] 나무 섭지

30 Apr 2023 in Algorithm on Algorithm

https://softeer.ai/app/assessment/index.html?xid=462511&xsrfToken=AbMlxmYXht6llfs3xqdq29IBMtrK1aUG&testType=practice

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

public class Main {
    static int[] dx = new int[]{-1,0,1,0};
    static int[] dy = new int[]{0,1,0,-1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String result = "No";
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] box = new char[n][m];
        int[] start = new int[2];

        Queue<int[]> q = new LinkedList<>();
        List<int[]> l = new ArrayList<>();

        for(int i = 0; i < n ; i++){
            String temp = sc.next();
            for(int j = 0 ; j < m; j++){
                box[i][j] = temp.charAt(j);
                if(box[i][j] == 'N') q.offer(new int[]{i,j});
                else if(box[i][j] == 'G') l.add(new int[]{i,j});
            }
        }

        for( int[] i : l ) q.offer(i);

        while(!q.isEmpty()){
            int[] temp = q.poll();
            char type = box[temp[0]][temp[1]];

            for(int i = 0 ; i < 4 ; i++){
                int nx = temp[0] + dx[i];
                int ny = temp[1] + dy[i];

                if(nx >= 0 && ny >= 0 && nx < n && ny < m){
                    if( type == 'G' && box[nx][ny] != 'G' ){
                        box[nx][ny] = 'G';
                        q.offer(new int[]{nx,ny});
                    }else if( type == 'N' && box[nx][ny] == 'D'){
                        result = "Yes";
                        break;
                    }else if( type == 'N' && box[nx][ny] == '.'){
                        box[nx][ny] = 'N';
                        q.offer(new int[]{nx,ny});
                    }
                }
            }

            if(result.equals("YES")) break;
        }

        System.out.println(result);
    }
}