[BOJ] 2573. 빙산

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

2573번: 빙산

 

1. 해결방법

BFS로 해결했다.

빙산이 모두 사라질 때를 카운트 해서 출력해야하므로, while문을 사용해서 year 카운트 변수를 루프때마다 +1하는 로직을 구상하였다.

또한, BFS를 돌면서 빙산의 그룹 카운팅을 하고 나서 빙산의 크기를 줄이는 로직을 추가해서 시간 복잡도를 최소한으로 줄였다.

 

1- 1. BFS 로직

def bfs(y, x):
    q = deque()
    q.append((y, x))
    chk[y][x] = True
    sea_list = []

    while q:
        ey, ex = q.popleft()
        sea = 0
        for d in range(4):
            ny, nx = ey + dy[d], ex + dx[d]
            if 0 <= ny < N and 0 <= nx < M:
                if graph[ny][nx] == 0:
                    sea += 1
                elif graph[ny][nx] != 0 and chk[ny][nx] == False:
                    chk[ny][nx] = True
                    q.append((ny, nx))
        else:
            if sea > 0:
                sea_list.append((ey, ex, sea))

    for y, x, sea in sea_list:
        graph[y][x] = max(0, graph[y][x] - sea)

1. 빙산의 인덱스 위치를 받아온다.
2. sea_list라는 리스트를 생성해서 해당 빙산의 위치에 동서남북 방향으로 바다가 몇 군데 있는지 체크하기 위한 리스트를 생성.
3. q가 빌 때까지 돌면서 동서남북 방향으로 빙하의 그룹을 체크, 유효검 검사도 필수
4. 만약 바다일 경우, sea라는 변수를 +1 한다.
5. 바다가 아닐 경우, 빙산이라는 말이기 때문에 q에 append 한다.
5. sea가 0 이상일 경우 (바다가 있었을 경우) sea_list에 인덱스 정보와 sea 변수 값을 append.
6. q 반복문이 끝났을 때, graph[][]에 sea 값만큼 감소.

 

 

2. 정답코드

import sys
from collections import deque

input = sys.stdin.readline


N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

dy, dx = (1, -1, 0, 0), (0, 0, 1, -1)



def bfs(y, x):
    q = deque()
    q.append((y, x))
    chk[y][x] = True
    sea_list = []

    while q:
        ey, ex = q.popleft()
        sea = 0
        for d in range(4):
            ny, nx = ey + dy[d], ex + dx[d]
            if 0 <= ny < N and 0 <= nx < M:
                if graph[ny][nx] == 0:
                    sea += 1
                elif graph[ny][nx] != 0 and chk[ny][nx] == False:
                    chk[ny][nx] = True
                    q.append((ny, nx))
        else:
            if sea > 0:
                sea_list.append((ey, ex, sea))

    for y, x, sea in sea_list:
        graph[y][x] = max(0, graph[y][x] - sea)


year = 0
while True:
    chk = [[False] * M for _ in range(N)]

    count = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] != 0 and chk[i][j] == False:
                bfs(i, j)
                count += 1

    if count >= 2:
        print(year)
        break
    else:
        # 빙산이 다 녹아서 없어질 경우,
        flag = 0
        for i in range(N):
            for j in range(M):
                if graph[i][j] != 0:
                    flag = 1
                    break
            if flag == 1:
                break
        else:
            print(0)
            exit(0)

    year += 1