10709번: 기상캐스터

문제

H × W 크기의 직사각형 격자 모양의 하늘이 있습니다. 각 구역에는 구름이 있을 수도('c'), 없을 수도('.') 있습니다. 모든 구름은 1분이 지날 때마다 동쪽(오른쪽)으로 1킬로미터씩 이동합니다. 각 구역에 대해 지금부터 몇 분 뒤에 처음으로 구름이 오는지 예측하는 문제입니다.

• 처음부터 구름이 떠 있는 구역은 0분 뒤에 구름이 옵니다.
• 구름이 영영 오지 않는 구역은 -1을 출력합니다.
• 입력: 첫째 줄에 H와 W가 주어지고, 둘째 줄부터 H개의 줄에 하늘의 상태가 주어집니다.
• 출력: 각 구역에 구름이 도달하는 시간을 H개의 줄에 걸쳐 공백으로 구분하여 출력합니다.

풀이

구름이 동쪽(오른쪽)으로만 이동한다는 점을 활용하여, 각 행(row)을 독립적으로 좌측에서 우측으로 탐색하며 해결할 수 있습니다.

1. 결과 배열 초기화: 모든 구역에 구름이 오지 않는다고 가정하여, 정답을 담을 ans 배열을 -1로 가득 채워 초기화(Arrays.fill)합니다.
2. 구름 위치 탐색 및 거리 계산: 각 행의 왼쪽부터 오른쪽으로 이동하며 구름('c')을 찾습니다. 구름을 발견하면 해당 위치의 ans 값을 0으로 설정합니다. 그 후, 구름의 오른쪽 구역들을 하나씩 확인(nx)하며 다음 구름을 만나거나 격자의 끝에 도달할 때까지 이전 위치의 시간 + 1(ans[i][nx - 1] + 1)을 기록합니다.
3. 이렇게 하면 한 번의 행 탐색으로 해당 행의 구름 이동 시간을 모두 정확하게 계산할 수 있습니다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int h = Integer.parseInt(st.nextToken());
       int w = Integer.parseInt(st.nextToken());
       
       // 하늘의 상태 입력
       char[][] a = new char[h][w];
       for (int i = 0; i < h; i++) {
          a[i] = br.readLine().toCharArray();
       }

       // 정답 배열을 -1로 초기화 (구름이 오지 않는 경우)
       int[][] ans = new int[h][w];
       for (int i = 0; i < h; i++) {
          Arrays.fill(ans[i], -1);
       }

       // 각 행마다 좌에서 우로 탐색
       for (int i = 0; i < h; i++) {
          for (int j = 0; j < w; j++) {
             // 구름을 발견한 경우
             if (a[i][j] == 'c') {
                ans[i][j] = 0; // 현재 위치는 0분
                
                int nx = j + 1;
                // 오른쪽으로 이동하며 다음 구름을 만나기 전까지 시간 증가
                while (nx < w && a[i][nx] != 'c') {
                   ans[i][nx] = ans[i][nx - 1] + 1;
                   nx++;
                }
             }
          }
       }

       // 결과 출력
       for (int i = 0; i < h; i++) {
          for (int j = 0; j < w; j++) {
             bw.write(ans[i][j] + " ");
          }
          bw.write("\n");
       }

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

구현 (Implementation), 시뮬레이션 (Simulation)