백준 2573 빙산

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

2573번: 빙산

📌 시간을 많이 쓴 이유

시간초과를 해결하느라 시간을 좀 많이 썼다..

pypy3 으로 제출해도 시간초과가 나서 음..큰일났네 생각하고 문제점을 찾기 시작했다.

시간초과 해결순서

iceberg_melts() 라는 함수를 만들어서 1년마다 그래프를 돌면서 상하좌우에 0이 있으면 -1 을 해준다 ->

visited 2차원 배열을 만들어서 중복해서 녹일수 없도록 한다 ->

year를 1증가지키고 덩어리의 수를 찾기 위해서 bfs 탐색을 시작한다 ->

group_cnt 가 1 보다 그면 year 출력 후 종료 

 

📌 시간초과 코드

 

from collections import deque
import sys

input = sys.stdin.readline


def iceberg_melts():
    for x in range(row):
        for y in range(col):
            if iceberg[x][y] > 0:
                visited[x][y] = True
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if (
                        0 <= nx < row
                        and 0 <= ny < col
                        and iceberg[nx][ny] == 0
                        # 현재 빙하에서 상하좌우에 있는 빙하중에 같은 해에 녹아서 0이 되버린 빙하에 영향을 받으면 안되므로 따로 방문처리를 해준다.
                        and not visited[nx][ny]
                    ):
                        if iceberg[x][y] >= 1:
                            iceberg[x][y] -= 1


def bfs(x, y):
    que = deque()
    que.append((x, y))
    visited[x][y] = True

    while que:
        x, y = que.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if (
                0 <= nx < row
                and 0 <= ny < col
                and iceberg[nx][ny] > 0
                and not visited[nx][ny]
            ):
                visited[nx][ny] = True
                que.append((nx, ny))


if __name__ == "__main__":
    row, col = map(int, input().split())
    iceberg = [list(map(int, input().split())) for _ in range(row)]
    year = 0
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    while True:
        group_cnt = 0
        visited = [[False] * col for _ in range(row)]
        # 시간초과의 원인, bfs 안에서 한번에 해결할 수 있다.
        iceberg_melts()
        year += 1
        # 덩어리의 수를 구하는 bfs 를 호출하기 전에 방문처리 2차원 배열을 다시 초기화 해준다.
        visited = [[False] * col for _ in range(row)]
        for i in range(row):
            for j in range(col):
                if iceberg[i][j] > 0 and not visited[i][j]:
                    group_cnt += 1
                    bfs(i, j)

        if group_cnt == 0:
            print(0)
            break

        if group_cnt >= 2:
            print(year)
            break

 

위의 해결순서에서 아마 iceberg_melts() 함수를 계속해서 호출하는것이 시간초과의 원인이였던 것 같다.

bfs 탐색을 한번 해주면 1년에 빙산을 얼마나 녹일지와 덩어리의 수를 한번에 찾을 수 있었다!

bfs 안에서 빙산을 녹일수 있는 높이를 저장해두는 배열을 추가로 만들면 시간초과 코드처럼 방문처리를 해주지 않아도 돼서 더 효율적으로 풀 수 있다.

 

📌 코드

from collections import deque
import sys

input = sys.stdin.readline


def bfs(x, y):
    que = deque()
    que.append((x, y))
    visited[x][y] = True

    while que:
        x, y = que.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if iceberg[nx][ny] > 0 and not visited[nx][ny]:
                visited[nx][ny] = True
                que.append((nx, ny))
            elif iceberg[nx][ny] == 0:
                melt_count[x][y] += 1


if __name__ == "__main__":
    row, col = map(int, input().split())
    iceberg = [list(map(int, input().split())) for _ in range(row)]
    year = 0
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    while True:
        group_cnt = 0
        melt_count = [[0] * col for _ in range(row)]
        visited = [[False] * col for _ in range(row)]

        for i in range(row):
            for j in range(col):
                if iceberg[i][j] > 0 and not visited[i][j]:
                    group_cnt += 1
                    bfs(i, j)

        if group_cnt == 0:
            print(0)
            break
        if group_cnt > 1:
            print(year)
            break
		# 덩어리의 수가 1개이면 year을 1년 증가 시키고 다음 탐색 진행.
        for i in range(row):
            for j in range(col):
                iceberg[i][j] -= melt_count[i][j]
                if iceberg[i][j] < 0:
                    iceberg[i][j] = 0

        year += 1

 

🧐 짚고 넘어가자 

 

녹일 수 있는 빙산의 높이를 저장해두는 2차원 배열을 따로 만드는것을 생각해내는게 이 문제를 푸는 핵심인것 같다.

빙산을 모두 녹이려면 높이가 있는 빙산을 모두 방문해야한다.

bfs 탐색도 마찬가지로 덩어리의 수를 세려면 높이가 있는 빙산을 모두 방문해야한다.

그렇다면 이 두개를 하나의 함수에서 묶어서 해결할 수 있지 않을까..? 라는 생각을 문제 풀면서 해봤으면 어땠을까 싶다..

앞으로 반복된 작업을 하나의 함수에서 해결할 수 있도록 생각해보면서 그래프 탐색을 풀어봐야겠다 !!