SWEA 10966. 물놀이를 가자

2차원 격자에서 땅에서 가장 가까운 물까지의 거리의 합을 구하는 문제이다.

 

물을 기준으로 모든 격자를 방문하면서 거리를 저장 후 이동한다. BFS를 적용하며 거리를 저장하면서 방문한 곳은 다시 방문하지 않게 한다.

int sum = 0;
int[][] distances = new int[n][m];
Deque<int[]> queue = new ArrayDeque<>();
for(int i=0; i<n; i++) {
    String line = br.readLine();
    for(int j=0; j<m; j++) {
        board[i][j] = line.charAt(j);
        if(board[i][j] == 'W') {
            distances[i][j] = 0;
            queue.add(new int[] {i, j});
        } else distances[i][j] = -1;
    }
}
            
while(!queue.isEmpty()) {
    int[] current = queue.remove();
    for(int k=0; k<4; k++) {
        int nr = current[0] + dr[k], nc = current[1] + dc[k];
        if(nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                    
        if(nr >= 0 && nr < n && nc >= 0 && nc < m && distances[nr][nc] == -1) {
            distances[nr][nc] = distances[current[0]][current[1]] + 1;
            sum += distances[nr][nc];
            queue.add(new int[] {nr, nc});
        }
    }
}
            
sb.append(sum).append('\n');

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
            char[][] board = new char[n][m];
           
            int sum = 0;
            int[][] distances = new int[n][m];
            Deque<int[]> queue = new ArrayDeque<>();
            for(int i=0; i<n; i++) {
                String line = br.readLine();
                for(int j=0; j<m; j++) {
                    board[i][j] = line.charAt(j);
                    if(board[i][j] == 'W') {
                        distances[i][j] = 0;
                        queue.add(new int[] {i, j});
                    } else distances[i][j] = -1;
                }
            }
            
            while(!queue.isEmpty()) {
                int[] current = queue.remove();
                for(int k=0; k<4; k++) {
                    int nr = current[0] + dr[k], nc = current[1] + dc[k];
                    if(nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                    
                    if(nr >= 0 && nr < n && nc >= 0 && nc < m && distances[nr][nc] == -1) {
                        distances[nr][nc] = distances[current[0]][current[1]] + 1;
                        sum += distances[nr][nc];
                        queue.add(new int[] {nr, nc});
                    }
                }
            }
            
            sb.append(sum).append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
}