[코드트리/INTERMEDIATE LOW] 비를 피하기(JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 가중치가 동일한 그래프에서의 BFS

 

각 사람마다 BFS를 수행해 가장 가까운 쉘터를 구하도록 했다.

⇨  시간 복잡도 : O(hN^2)

 

1. 격자를 입력받으면서, 사람(2)의 위치도 리스트에 저장해둔다.

2. 사람 위치가 저장된 리스트를 돌면서, 각 사람이 비를 피할 수 있는 공간 3까지 가는 최단 거리를 bfs를 통해 구한다.  

• 방문 배열을 매번 초기화해줘야 한다.
• 사람 위치(2)에서 bfs를 진행하며 3까지 bfs를 수행한다. (=최단 거리)
• 큐에는 (방문할 행, 열, 거리 값)을 저장해 들고 다니고, 거리 값은 다음 칸으로 이동할 때 거리 값 갱신 시 사용 가능하다.

q.add(new int[] {nx, ny, now[2] + 1});

 

 

 

💥 유의사항

거리 값 갱신할 떄 변수 cnt 무작정 사용하면 갱신이 되지 않는다...

누적한 값 사용하기,,

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int n,h,m;
    static int[][] arr, ans;
 
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static boolean[][] visited;
 
    static List<int[]> peoplePos = 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());   // 격자 크기
        h = Integer.parseInt(st.nextToken());   // 사람 수
        m = Integer.parseInt(st.nextToken());   // 비 피할 수 있는 공간 갯수
 
        arr = new int[n][n];
        visited = new boolean[n][n];
 
        for(int i = 0 ; i < n ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < n ; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
 
                if(arr[i][j] == 2) peoplePos.add(new int[] {i, j});
            }
        }
        
        ans = new int[n][n];
 
        for(int[] p : peoplePos) {
            init();
            bfs(p[0], p[1]);
        }
 
        printAns();        
    }
 
    private static void bfs(int x, int y) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y, 0}); // 🔔 큐에 (방문할 행, 열, 거리) 넣기
 
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
 
            for(int dir = 0 ; dir < 4 ; dir++) {
                int nx = now[0] + dx[dir];
                int ny = now[1] + dy[dir];
 
                if(canGo(nx, ny)) {
                    if(arr[nx][ny] == 3) {
                        ans[x][y] = now[2] + 1;
                        return;
                    }
 
                    visited[nx][ny] = true; // 방문 표시
                    q.add(new int[] {nx, ny, now[2] + 1});  // 🔔 거리 값 갱신
                }
            }
        }
 
        ans[x][y] = -1; // 벽 못 마주치면 그 사람은 -1
    }
 
    private static void printAns() {
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++)
                sb.append(ans[i][j] + " ");
            sb.append("\n");
        }
        
        System.out.println(sb);
    }
 
    private static void init() {
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++) {
                visited[i][j] = false;
            }
        }
    }
 
    private static boolean canGo(int x, int y) {
        return (inRange(x, y) && !visited[x][y] && arr[x][y] != 1);
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < n && 0 <= y && y < n);
    }
}

 

 

➕ 다른 풀이 방식

M개의 쉘터를 시작으로 하는 BFS를 한 번만 수행하면 된다고 한다.

여러 시작점을 두고 최단거리를 기록하면, 각 칸으로부터 가장 가까운 시작점까지의 거리를 구할 수 있다고 한다.

⇨ 시간 복잡도 : O(N^2)

 

WHY?

> BFS의 큐가 시작점으로부터 거리가 더 가까운 정점들을 먼저 빼주므로

---

💦 어려웠던 점

거리 값 갱신할 떄 변수 cnt를 활용하려고 했는데 정확하게 답이 반영되지 않았다..

누적한 값 사용하며 값 갱신하기,,

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리