문제 풀이(43)

https://www.acmicpc.net/problem/16441

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


class Node{
    int x;
    int y;

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

public class Main {

    static int N, M;
    static char[][] map;
    static boolean[][] visited;
    static int[][] dist;
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    static ArrayList<Node>wolf = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        
        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];

        visited = new boolean[N][M];

        dist = new int[N][M];

        Node start = null;

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            
            for (int j = 0; j < M; j++) {

                if(s.charAt(j) == 'W')wolf.add(new Node(i, j));
                if(s.charAt(j) == '#')dist[i][j] = 1;
                if(s.charAt(j) == '+')dist[i][j] = 1;
                map[i][j] = s.charAt(j);
            }

            
        }

        for (int i = 0; i < wolf.size(); i++) {
            
            dist[wolf.get(i).x][wolf.get(i).y] = 1;

            bfs(wolf.get(i));

        }

       

        ArrayList<Node>list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (dist[i][j] == 0) {
                    list.add(new Node(i, j));
                }

                
            }
           
        }

       

        for (int i = 0; i < list.size(); i++) {
            
            map[list.get(i).x][list.get(i).y] = 'P';

        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    public static void bfs(Node node)
    {
        Queue<Node>Q = new LinkedList<>();

        Q.offer(node);

        visited[node.x][node.y] = true;

        while (!Q.isEmpty()) {
            Node now = Q.poll();


            for (int k = 0; k < dir.length; k++) {

                if (map[now.x][now.y] == '+') {
                    
                    dist[now.x][now.y] = 1;

                    Node res = function(now.x, now.y, k);

                    if (visited[res.x][res.y]) {
                        continue;
                    }

                    visited[res.x][res.y] = true;

                    dist[res.x][res.y] = 1;

                    Q.offer(new Node(res.x, res.y));

                }else{
                
                
                    int nx = now.x + dir[k][0];
                
                    int ny = now.y + dir[k][1];

                
                    if (visited[nx][ny]) {
                
                        continue;
                
                    }

                
                    if (nx < 0 && nx >= N && ny < 0 && ny >= M) {
                
                        continue;
                
                    }

                
                    if (map[nx][ny] == '#') {
                
                        dist[nx][ny] = 1;

                        continue;
                
                    }

                
                    if (map[nx][ny] == '.') {
                
                        Q.offer(new Node(nx, ny));
                
                        visited[nx][ny] = true;

                        dist[nx][ny] = 1;
                
                        continue;
                
                    }

                    if (map[nx][ny] == '+') {
                    
                        dist[nx][ny] = 1;

                  
                        Node res = function(nx, ny, k);


                    
                        if (visited[res.x][res.y]) {
                    
                            continue;
                    
                        }

                    
                        visited[res.x][res.y] = true;

                    
                        Q.offer(new Node(res.x, res.y));

                        dist[res.x][res.y] = 1;
               
                
                    }

                }
            }

        }
    }

    public static Node function(int x, int y, int k)
    {

        while (
        x + dir[k][0] >= 0 && x + dir[k][0] < N && y + dir[k][1] >= 0 && y + dir[k][1] < M
        && map[x + dir[k][0]][y + dir[k][1]] != '#'    
        ) {
            x += dir[k][0];
            y += dir[k][1];

            dist[x][y] = 1;

            if (map[x][y] == '.') {
                break;
            }
        }

        return new Node(x, y);
    }
}

main 메서드:
늑대 위치와 장애물을 dist 배열에 1로 표시한다.
각 늑대 위치에서 bfs 메서드를 호출하여 BFS를 실행하여 늑대가 도달 가능한 위치를 식별한다.
늑대가 도달할 수 없는 모든 위치를 dist 배열을 통해 식별하고, 이러한 위치를 'P'로 표시하여 결과를 출력한다.

bfs 메서드:
너비 우선 탐색 (BFS) 알고리즘을 사용하여 주어진 노드에서 늑대가 도달 가능한 모든 위치를 식별한다.
방문한 위치를 표시하고, dist 배열을 사용하여 거리 정보를 저장한다.
늑대가 감지되면 해당 지점을 dist 배열에 1로 표시한다.

function 메서드:
주어진 방향 (k)으로 이동 가능한 최대 거리를 찾는 메서드이다. 이동 중에 장애물 (#)을 만나거나 지정한 범위를 벗어날 때까지 이동한다.
이동 중에 해당 위치를 dist 배열에 1로 표시한다.