[SWEA] 10966. 물놀이를 가자 (BFS/Java)

[SWEA] 10966. 물놀이를 가자

 

📌 문제 풀이

각 땅(L)에서 가장 가까운 물(W)까지의 최소 거리를 구하고, 그 거리들의 합을 계산해야 한다.

처음에 문제에서 적힌 것 처럼 땅에서 출발해서 물에 도착하는 경우 그 거리를 누적하게 했는데 시간 초과가 떴다.

 

문제에선 물(W)의 개수가 최소 1개 이상 주어진다고 했지만,

예외적으로 최악의 상황을 생각해보자!!

 

만약 물(W)이 아예 없다면, 땅(L) 위치에서 각각 BFS를 수행해도 물에 도착할 수 없게된다.

이 경우 모든 땅에 대해 개별적으로 BFS를 수행해야 하므로, 땅의 개수만큼 BFS가 실행되어

연산량이 크게 증가하고 최단 거리 계산이 불가능해진다.

따라서 물(W)의 위치에서 출발해, 동시에 BFS를 수행하면서 땅(L)을 탐색하는 방식으로
생각의 전환이 필요하다 !!!!!!!!

이렇게 풀이하면 모든 땅(W)이 한번에 가장 가까운 물(L)에 도달해 최단 거리를 계산하므로 연산 효율성이 개선된다.

 

✨ 제출 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {

    static int T, N, M, ans;
    static char[][] map;
    static boolean[][] check;
    static Queue<int[]> q;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(in.readLine());

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            map = new char[N][M];
            check = new boolean[N][M];
            q = new LinkedList<>();

            // 지도 입력과 동시에 'W'인 위치를 큐에 추가
            for (int i = 0; i < N; i++) {
                String str = in.readLine();
                for (int j = 0; j < M; j++) {
                    map[i][j] = str.charAt(j);
                    if (map[i][j] == 'W') {
                        check[i][j] = true;
                        q.offer(new int[]{i, j, 1}); // 모든 'W' 위치를 큐에 추가, 거리 1로 초기화
                    }
                }
            }

            ans = 0;
            bfs();
            sb.append("#" + tc + " " + ans).append("\n");
        }
        System.out.print(sb.toString());
    }


    static void bfs() {

        while (!q.isEmpty()) {
            int[] cur = q.poll();

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

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

                if (!check[nx][ny]) {
                    check[nx][ny] = true;
                    q.offer(new int[]{nx, ny, cnt + 1});
                    ans += cnt;
                }
            }
        }
    }

}