[CodeTree/Python] 확산4

문제

확산 4

크기가 n x m 인 표 위에 채워져 있는 칸은 'O'로 빈칸은 ' . ' 으로 주어져 있습니다.

'O' 는 다음과 같은 속성을 가집니다.

• 3초가 지나게 되면 자신을 포함한 상하좌우 5개의 칸을 빈칸으로 만듭니다.

또, 'O'는 다음과 같은 규칙으로 생기게 됩니다.

• 초기 1초를 제외하고, 모든 빈칸에 'O'가 생깁니다.

s초 후에 표의 상태를 구하는 프로그램을 작성해보세요.

 

입력 형식

첫 번째 줄에 n, m, s가 주어집니다.

두 번째 줄부터 n개의 줄에 걸쳐 ' . ' 또는 'O' 이 m개씩 공백없이 주어집니다.

• 1 ≤ n, m, s ≤ 200

출력 형식

s초 후의 표의 상태를 n개의 줄에 걸쳐 출력합니다.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

해결

# %2 == 0 : 모두 O
# 3초 후 부터 +3 단위(3, 7, 11 ...)
# 5초 후 부터 +3 단위(5, 9, 13 ...)

from collections import deque

n, m, s = map(int, input().split())
graph = [list(map(str, input())) for _ in range(n)]


def simulate(n, m, s, graph):
    if s == 1:
        return graph
    elif s % 2 == 0:
        return [['O'] * m for _ in range(n)]
        
    def bfs(graph):
        Q = deque()
        
        # 방문 리스트 초기화
        for i in range(n):
            for j in range(m):
                if graph[i][j] == 'O':
                    Q.append((i, j))

        dx = [-1, 0, 1, 0] # 북쪽부터 시계방향
        dy = [0, 1, 0, -1]
        
        fin_graph = [['O'] * m for _ in range(n)]
        while Q:
            x, y = Q.popleft()
            
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]

                if 0 <= nx < n and 0 <= ny < m:
                    fin_graph[x][y] = '.'
                    fin_graph[nx][ny] = '.'
        return fin_graph


    three_seconds = bfs(graph)
    five_seconds = bfs(three_seconds)

    return three_seconds if s % 4 == 3 else five_seconds


ans = simulate(n, m, s, graph)
for i in range(n):
    for j in range(m):
        print(ans[i][j], end = '')
    print()

 

    BFS + 시간 흐름에 따른 변화를 구현해야 하는 문제이다. 출력 결과와 조건을 확인하고 다음을 고려하여 작성하였다.

1. 2초 단위, 3초 단위, 5초 단위(3초부터 +3초이므로) 3가지로 케이스를 분리한다.
2. 큐를 생성하여 'O'인 경우 좌표를 큐에 넣는다.
3. 3초 단위부터 BFS를 돌아야 하므로, 2초의 전체가 'O'인 경우에 대한 그래프를 생성한다.
4. 큐에서 인접 리스트를 돌면서 자기 자신을 포함하여 '.'로 변경한다.
5. 3초 단위 케이스에서는 초기 그래프에서 BFS를 실행하고, 5초 단위는 3초 단위 케이스에서 새로운 BFS를 진행한다.

실행 결과

 

(tmi)

여기서 빡종함