2573

날짜 : 2023. 03. 24

사용 언어 : python

 

문제

 

 

코드

import copy
import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())  # 행, 열
graph = list()
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for _ in range(n): graph.append(list(map(int, sys.stdin.readline().split())))
year = 0


def bfs(r, c):
    q = deque()
    q.append([r, c])
    while q:
        now = q.popleft()
        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]
            if nx in range(n) and ny in range(m):  # 범위에 포함
                if graph[nx][ny] > 0 and not visited[nx][ny]:  # 연결, 방문처리 x
                    visited[nx][ny] = True
                    q.append([nx, ny])
    return


while True:
    temp = copy.deepcopy(graph)
    for i in range(n):
        for j in range(m):
            if graph[i][j] > 0:
                for k in range(4):
                    x = i + dx[k]
                    y = j + dy[k]
                    if x in range(n) and y in range(m):  # 범위 포함
                        if graph[x][y] == 0:  # 바다와 인접
                            temp[i][j] -= 1  # 녹음
            if temp[i][j] < 0: temp[i][j] = 0
    graph = copy.deepcopy(temp)
    cnt = 0  # 섬의 개수
    visited = [[False] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if graph[i][j] > 0 and not visited[i][j]:
                visited[i][j] = True
                bfs(i, j)
                cnt += 1
    """for i in graph:
        print(i)
    print()"""
    if cnt >= 2:
        print(year+1)
        break
    elif cnt == 0:
        print(0)
        break
    else:
        year += 1

 

 

풀이

- 조건에 따라 입력받은 후 1년 경과 후 녹인 다음 그 섬들의 그룹을 DFS 또는 BFS를 활용하여 구한다.

 

 

알게된 점

- 녹는 과정에서 단일 그래프로 진행하는 경우 기존에 얼음이었던 구역이 0이 되어 이후 반복문에 영향을 미치는 케이스가 존재했다.

- 그래서 임시의 그래프 temp를 생성 후 graph를 기준으로 인접구역 개수에 따라 temp에 연산 후 깊은복사를 통해 녹은 값들을 최신화했다.

 

 

참고 사이트

-