백준 2573 빙산 - 골드4 [파이썬]

https://www.acmicpc.net/problem/2573

2573번: 빙산

 

시간초과로 못풀었던 문제였는데, 이제는 풀 수 있을까 해서 다시 도전해봤다.

그래프이론, 구현이 동시에 들어간 문제이다.

 

시간을 단축시키기 위해 모든 맵을 돌면서 섬의 개수를 세는 동시에,

rlist 라는 배열에 바로 줄여야할 값을 추가해나갔다.

(rlist에 기억해놓는 방식이 아닌, 바로 줄여버리면 바다가 아닌데, 바다로 착각해서 오류난다)

 

섬의 개수를 셀 때는 BFS를 사용했다.

 

그리고 한바퀴 다돌면 rlist에 기억해놓은 내용으로

graph의 값을 줄였다.

 

다 풀었다고 생각해서 제출했지만

빙하가 다 녹아서 사라질때까지 섬이 2개 이상으로 나눠지지 않는 예외처리를 잊어먹어서

1회 틀렸다 ㅠ 역시 문제는 꼼꼼히 읽자.

 

정답 소스코드

import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int, input().split(" "))

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
graph = []
for i in range(R):
    graph.append(list(map(int, input().split(" "))))

answer = 0
queue = deque()
while True:
    visited = [[False for i in range(C)] for i in range(R)]
    islandCnt = 0
    rlist = []
    for r in range(1, R):
        for c in range(1, C):
            if graph[r][c] != 0 and visited[r][c] == False:
                visited[r][c] = True
                queue.append((r, c))
                islandCnt += 1
                while queue:
                    rr, cc = queue.popleft()
                    zeroCnt = 0
                    for i in range(4):
                        nr = rr + dr[i]
                        nc = cc + dc[i]
                        if graph[nr][nc] == 0:
                            zeroCnt += 1
                        if graph[nr][nc] != 0 and visited[nr][nc] == False:
                            queue.append((nr, nc))
                            visited[nr][nc] = True
                    rlist.append((rr, cc, zeroCnt))

    # 만약 빙하 개수가 2개 이상이다?
    if islandCnt >= 2:
        print(answer)
        break

    # 만약 빙하가 다 녹아서 사라졌는데 빙하 개수가 2개를 넘은적이 없다?
    if len(rlist) == 0:
        print(0)
        break

    # 빙하 녹이기
    for rval in rlist:
        r, c, cnt = rval[0], rval[1], rval[2]
        graph[r][c] -= cnt
        if graph[r][c] < 0:
            graph[r][c] = 0

    answer += 1

결과

예전엔 자바로 알고리즘을 풀곤 했었다..