[PS] 백준 10709 기상캐스터

이번에는 백준 10709번 기상캐스터 문제를 풀어보았습니다.

이 문제는 현재 구름 위치가 주어졌을 때, 각 칸에 구름이 처음 도착하는 시간이 몇 분 뒤인지를 구하는 문제입니다.

핵심은 구름이 매분 동쪽으로 한 칸씩 이동한다는 점을 이용해서, 각 행을 왼쪽에서 오른쪽으로 한 줄씩 처리하는 것이었습니다.

---

문제 설명

H x W 크기의 도시가 있고, 각 칸에는 현재 구름이 있을 수도 있고 없을 수도 있습니다.

• c : 현재 구름이 있는 칸
• . : 현재 구름이 없는 칸

모든 구름은 1분마다 동쪽으로 한 칸씩 이동합니다.

도시 밖에서 새로운 구름이 들어오지는 않습니다.

각 칸에 대해

• 처음부터 구름이 있으면 0
• 몇 분 뒤에 처음 구름이 오면 그 시간
• 끝까지 구름이 오지 않으면 1

을 출력하면 됩니다.

---

풀이 아이디어

이 문제는 각 행을 독립적으로 보면 훨씬 단순해집니다.

어떤 행에서 왼쪽부터 오른쪽으로 보면서,

• 아직 앞에서 구름을 한 번도 못 봤다면 현재 칸은 1
• 앞에서 구름을 본 적이 있다면 그 구름이 현재 칸까지 오는 시간을 계산
• 현재 칸에 구름이 있다면 시간은 0

으로 처리할 수 있습니다.

즉, 각 행마다 time 값을 하나 두고,

• 구름을 만나기 전에는 1
• 구름을 만나면 0
• 그 뒤 빈칸을 만날 때마다 1, 2, 3 ...

으로 증가시키는 방식으로 해결할 수 있습니다.

---

코드

#include <bits/stdc++.h>
using namespace std;
int sky[100][100];
int H, W;
int main() {

   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);

   cin >> H >> W;

   for (int i = 0; i < H; i++) {
       string temp;
       cin >> temp;
       for (int j = 0; j < W; j++) {
           if (temp[j] == 'c')
               sky[i][j] = 1;
           else
               sky[i][j] = 0;
       }
   }

    int time = -1;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (!sky[i][j]) {
                if (time == -1)
                    sky[i][j] = time;
                else {
                    time++;
                    sky[i][j] = time;
                }
            } else {
                time = 0;
                sky[i][j] = time;
            }
        }
        time = -1;
    }

    for (int i=0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cout << sky[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

---

풀이 흐름

1. 입력 문자열을 받아서 구름이 있는 칸은 1, 없는 칸은 0으로 sky 배열에 저장한다.
2. 각 행마다 왼쪽부터 오른쪽으로 순회한다.
3. 현재 칸이 구름이 없는 칸이라면
   • 아직 구름을 본 적이 없으면 1
   • 앞에 구름이 있었다면 시간을 1 증가시켜 저장
4. 현재 칸이 구름이 있는 칸이라면 시간을 0으로 두고 저장한다.
5. 한 행 처리가 끝나면 time을 다시 1로 초기화한다.
6. 최종 결과를 출력한다.

---

구현 포인트

1. 먼저 구름 유무를 숫자로 바꾸어 저장

입력은 문자 형태로 들어오지만, 이후 계산은 숫자로 하는 편이 편하기 때문에 먼저 sky 배열에

• 구름이 있으면 1
• 없으면 0

으로 바꾸어 저장했습니다.

if (temp[j] == 'c')
    sky[i][j] = 1;
else
    sky[i][j] = 0;

이렇게 하면 이후 순회하면서 조건을 더 간단하게 처리할 수 있습니다.

---

2. 각 행을 왼쪽에서 오른쪽으로만 보면 됨

구름은 동쪽으로만 이동하므로, 현재 칸에 도착할 수 있는 구름은 같은 행의 왼쪽 칸들에 있던 구름뿐입니다.

그래서 각 행에 대해 왼쪽부터 오른쪽으로만 보면 됩니다.

즉, 한 행을 순회하면서 앞에서 구름을 봤는지와, 그 구름이 현재 칸까지 오는 데 몇 분 걸리는지만 관리하면 됩니다.

---

3. time 변수를 이용한 처리

이 코드에서는 time 변수를 사용해 현재 칸까지 구름이 오는 시간을 관리했습니다.

초기값은 -1입니다.

int time = -1;

의미는 다음과 같습니다.

• 1 : 아직 이 행에서 구름을 한 번도 만나지 못함
• 0 : 현재 칸에 구름이 있음
• 1 이상 : 앞의 구름이 현재 칸까지 오는 데 걸리는 시간

---

4. 구름이 없을 때 처리

현재 칸에 구름이 없으면 두 가지 경우로 나뉩니다.

if (!sky[i][j]) {
    if (time == -1)
        sky[i][j] = time;
    else {
        time++;
        sky[i][j] = time;
    }
}

• time == -1 이라면 앞에 구름이 한 번도 없었다는 뜻이므로 1
• time != -1 이라면 앞에 구름이 있었고, 현재 칸까지 오는 시간을 하나 증가시켜 저장

하는 방식입니다.

---

5. 구름이 있을 때 처리

현재 칸에 구름이 있다면 그 칸은 이미 구름이 있는 상태이므로 시간은 0입니다.

else {
    time = 0;
    sky[i][j] = time;
}

즉, 현재 칸에서부터 다시 시간이 시작되는 셈입니다.

---

6. 행이 바뀌면 time 초기화

한 행의 정보는 다른 행과 연결되지 않으므로,

행 하나를 다 처리한 뒤에는 time을 다시 -1로 초기화해야 합니다.

time = -1;

이렇게 해야 다음 행에서도 처음부터 새롭게 계산할 수 있습니다.

---