2468

날짜 : 2022. 11. 26

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque

def bfs(a, b):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    queue.append([a, b])
    while queue:
        t = queue.popleft()
        for i in range(4):
            x = t[0] + dx[i]
            y = t[1] + dy[i]
            if x in range(n) and y in range(n):  # 범위에 포함
                if land[x][y] > 0 and not visited[x][y]:  # 도달가능, 방문체크 안한 경우
                    visited[x][y] = True  # 방문체크
                    queue.append([x, y])  # 큐에 추가
    return


n = int(sys.stdin.readline())
land = list()
queue = deque()
for _ in range(n):
    land.append(list(map(int, sys.stdin.readline().split())))
    m = max(land[-1])
cnt = []

for _ in range(1, m+1):
    """for i in land:
        print(i)"""

    k = 0
    visited = [[False] * n for i in range(n)]
    for i in range(n):
        for j in range(n):
            if land[i][j] > 0 and not visited[i][j]:  # 높이가 있고 방문하지 않은 경우
                visited[i][j] = True  # 방문처리
                bfs(i, j)  # BFS
                k += 1  # 내륙 추가

    # 비가 옴(전부 1씩 감소)
    for i in range(n):
        for j in range(n):
            land[i][j] -= 1
            if land[i][j] < 0: land[i][j] = 0
    #print(k)
    #print()
    cnt.append(k)
print(max(cnt))

 

 

풀이

- 비가 온 뒤의 케이스를 따져보아야 하기 때문에 일반적인 BFS를 반복문에 넣어 물에 잠기는 것을 구현하였다.

- 그리고 강수량에 따른 섬의 개수를 저장하는 리스트를 만든 후 해당 값들을 저장, 마지막에 최댓값을 출력함으로써 문제를 해결했다.

 

 

알게된 점

- 되게.... 지저분하게 푼것같다..  ㅎㅎ

 

 

참고 사이트

-