[구현] 코딩테스트 문제 TIL (기상캐스터) - 백준 10709번

오늘 문제는 저번 문제와 약간 다른 좌표상에서 해결해야 하는 시뮬레이션 유형의 문제입니다. 그럼 살펴보도록 하겠습니다.

---

1. 오늘의 학습 키워드

• 구현
• 시뮬레이션

---

2. 문제: 10709. 기상캐스터

• 단계: 🥈 실버 5단계
• 주제:
  • 구현
  • 시뮬레이션
• 출처: https://www.acmicpc.net/problem/10709

문제

JOI시는 남북방향이 H 킬로미터, 동서방향이 W 킬로미터인 직사각형 모양이다. JOI시는 가로와 세로의 길이가 1킬로미터인 H × W 개의 작은 구역들로 나뉘어 있다. 북쪽으로부터 i 번째, 서쪽으로부터 j 번째에 있는 구역을 (i, j) 로 표시한다.

각 구역의 하늘에는 구름이 있을 수도, 없을 수도 있다. 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동한다. 오늘은 날씨가 정말 좋기 때문에 JOI시의 외부에서 구름이 이동해 오는 경우는 없다.

지금 각 구역의 하늘에 구름이 있는지 없는지를 알고 있다. 기상청에서 일하고 있는 여러분은 각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 예측하는 일을 맡았다.

각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 구하여라.

입력

입력은 1 + H 행으로 주어진다.

첫 번째 행에는 정수 H, W (1 ≦ H ≦ 100, 1 ≦ W ≦ 100) 가 공백을 사이에 주고 주어진다. 이것은 JOI시가 H × W 개의 작은 구역으로 나뉘어 있다는 것을 의미한다.

이어진 H 개의 행의 i번째 행 (1 ≦ i ≦ H) 에는 W문자의 문자열이 주어진다. W 개의 문자 중 j번째 문자 (1 ≦ j ≦ W) 는, 구역 (i, j) 에 지금 구름이 떠 있는지 아닌지를 나타낸다. 구름이 있는 경우에는 영어 소문자 'c' 가, 구름이 없는 경우에는 문자 '.' 가 주어진다.

출력

출력은 H 행으로, 각 행에는 공백으로 구분된 W 개의 정수를 출력한다. 출력의 i 번째 행 j 번째 정수 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는, 지금부터 몇 분후에 처음으로 구역 (i, j) 에 구름이 뜨는지를 표시한다. 단, 처음부터 구역 (i, j) 에 구름이 떠 있었던 경우에는 0을, 몇 분이 지나도 구름이 뜨지 않을 경우에는 -1을 출력한다.

예제 입력 1 복사

3 4
c..c
..c.
....

예제 출력 1 복사

0 1 2 0
-1 -1 0 1
-1 -1 -1 -1

예제 입력 2 복사

6 8
.c......
........
.ccc..c.
....c...
..c.cc..
....c...

예제 출력 2 복사

-1 0 1 2 3 4 5 6
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 1 2 0 1
-1 -1 -1 -1 0 1 2 3
-1 -1 0 1 0 0 1 2
-1 -1 -1 -1 0 1 2 3

힌트

입출력 예제 1에서는, JOI시가 3 × 4 개의 작은 구역으로 나뉘어 있다. 지금 JOI시의 구름 상황은 아래와 같다. 그림의 위쪽이 북쪽이다.

1분 간격으로 구름은 다음과 같이 움직인다.

---

3. 문제 풀이

Step1. 문제 이해하기

JOI시는 가로와 세로의 길이가 1킬로미터인 H x W개이 작은 구역들로 나뉘어 있습니다. 북쪽으로부터 i 번째, 서쪽으로부터 j 번째에 있는 구역을 (i, j)로 표시합니다.

각 구역의 하늘에는 구름이 있을 수도, 없을 수도 있습니다. 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동합니다. (즉, 오른쪽으로만 이동할 수 있습니다.)

오늘은 날씨가 정말 좋기 때문에 JOI시의 외부에서 구름이 이동해 오는 경우는 없다. → 즉, 좌표에서만 이동한다는 것을 의미합니다.

지금 각 구역의 하늘에 구름이 있는지 없는지를 알고 있습니다.

기상청에서 일하고 있는 여러분은 각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 예측하는 일을 맡았다고 합니다.

각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 구해야 합니다.

이 뜻은 각 좌표에 구름이 언제 오는지를 표기해라는 의미입니다.

문제가 길었는데요. 입출력을 살펴보도록 하겠습니다.

• Input:
  • 첫 번째 행에는 정수 H, W가 주어집니다.
    • H와 W는 1이상 100이하입니다.
  • 이어진 H개의 행의 i번째 항에는 W문자의 문자열이 주어집니다.
  • W개의 문제 중 j번째 문자는 구역 (i, j)에 구름이 떠 있는지를 아닌지를 나타냅니다.
    • 구름이 있는 경우에는 영어 소문자 ‘c’가, 구름이 없는 경우에는 문자 ‘.’가 주어집니다.
• Output:
  • 출력은 H행으로, 각 행에는 공백으로 구분된 W개의 정수를 출력합니다.
  • 출력의 i번째 행 j번째 정수는, 지금부터 몇 분후에 처음으로 구역 (i, j)에 구름이 뜨는지를 표시합니다.
    • 단, 처음부터 구역 (i, j)에 구름이 떠있었던 경우에는 0을, 몇 분이 지나도 구름이 뜨지 않을 경우에는 -1을 출력합니다.

Step2. 문제 분석하기

주어진 문제는 문제 상황을 직접 구현하여 그대로 따라가는 방식으로 시뮬레이션 문제라고 볼 수 있습니다.

문제를 살펴보면 구름은 오른쪽으로 이동하면서 각 구역 별로 구름이 언제 오는지를 표기하는 문제이기 때문에 좌표를 지정하고 구름의 상태 변화를 추적하면 해결할 수 있습니다.

몇 분이 지나도 구름이 뜨지 않을 경우에는 -1을 출력하라고 했습니다.

그렇기 때문에 좌표 설정의 초깃값을 -1로 지정하면 될 것 같습니다.

각 행의 열들을 순회하면서 현재 위치의 바로 전 위치가 -1이 아니고, 현재 위치가 -1이라면 구름이 온다는 것을 알 수 있습니다. 이 조건을 활용하여 코드를 구현하면 문제를 해결할 수 있습니다.

그럼 코드 설계를 해보도록 하겠습니다.

Step3. 코드 설계

• 입력 처리:
  • H, W: JOI시의 행과 열 크기를 입력받습니다.
  • state: 각 구역의 구름 상태를 입력받습니다. 각 행은 문자열로 이루어져 있습니다.
• 초기화:
  • 각 행의 열 정보를 담은 리스트 sky를 생성하고, 모든 값을 -1로 초기화합니다.
  • 1은 구름이 오지 않을 경우를 나타냅니다.
• 구름 상태 초기화:
  • 각 행의 열을 순회하며 현재 위치에 구름이 있는 경우('c'), 해당 위치를 0으로 설정합니다.
  • 이는 구름이 처음부터 있는 구역을 처리하는 부분입니다.
• 구름 이동 시간 계산:
  • 각 행의 두 번째 열부터 끝까지 순회하며:
    • 현재 위치가 -1이고, 바로 왼쪽 위치가 -1이 아니라면, 구름이 이동하여 도달할 수 있는 시간(sky[i - 1] + 1)을 기록합니다.
• 출력:
  • 계산된 sky 리스트를 공백으로 구분하여 출력합니다.

Step4. 코드 구현

import sys
H, W = map(int, sys.stdin.readline().split())
state = [sys.stdin.readline().strip() for _ in range(H)]

def sol(H, W, state):
    
    for s in state:
        sky = [-1] * len(s)
        for i in range(W):
            if s[i] == 'c':
                sky[i] = 0
        for i in range(1, W):
            if sky[i] == -1 and sky[i - 1] != -1:
                sky[i] = sky[i - 1] + 1
        print(*sky)
sol(H=H, W=W, state=state)    

• 코드 설명:
  1. 구름 초기화:
     • 첫 번째 for 루프에서 구름이 있는 구역('c')을 확인하고, 해당 위치의 값을 0으로 설정합니다.
     • 이 과정은 $O(W)$의 시간 복잡도를 가집니다.
  2. 구름 이동 시간 계산:
     • 두 번째 for 루프는 구름이 오른쪽으로 이동하며 각 구역에 도달하는 시간을 계산합니다.
     • 조건 sky[i] == -1 and sky[i - 1] != -1을 통해 구름이 새로 도달하는 구역만 처리합니다.
  3. 출력:
     • 각 행의 결과를 공백으로 구분하여 출력합니다.
• 시간 복잡도:

  1. 구름 초기화 및 이동 시간 계산:

     • 각 행에 대해 $O(W)$ 반복이 이루어집니다.
     • 총 $H$개의 행에 대해 수행되므로 $O(H \times W)$입니다.

  2. 입력 및 출력 처리:
     - 입력은 $O(H \times W)$이며, 출력도 $O(H \times W)$입니다.

     총 시간 복잡도: $O(H \times W)$

     ($H, W \leq 100$이므로 최대 $10,000$의 연산량으로 충분히 효율적입니다.)

• 결과:

---

4. 마무리

• 이 문제는 시뮬레이션 유형의 문제로, 각 구역의 구름 상태를 초기화한 뒤 구름 이동 시간을 계산하는 방식으로 해결했습니다.
• 구름이 언제 도달하는지를 나타내는 규칙을 반복적으로 적용하여, 각 행을 독립적으로 처리하였습니다.
• 문제의 제약 조건($H, W \leq 100$)을 고려해 완전 탐색으로도 효율적으로 해결할 수 있었습니다.

오늘 시뮬레이션의 기본 문제였습니다. 역시 시뮬레이션 문제는 반복만이 답이군요. 다양한 시뮬레이션 유형의 문제를 많이 연습하여, 더 익숙해지도록 해야겠습니다.

긴 글 읽어주셔서 감사합니다.