[백준] 2573번: 빙산 - 파이썬

🧩문제 해석

이제 이런 문제들을 딱 보면 그래프 관련 문제라는 걸 바로 알아차릴 수 있게 되었다.
'빙산 한 덩이가 주어졌을 때'가 조건에 들어가있으니, 무조건 빙산은 주어진다. 
그러면 이제 빙산에서 얼음의 위치와 그 얼음 주위 환경을 살피면 된다. 그리고 빙산이 쪼개졌는지 BFS를 통해 확인한다. 

 

🔉 풀이 전 잡담

앞서 말한 문제 해석을 알고리즘으로 구현해내는데에는 성공했다. 
첫번째 제출에는 런타임 에러(RecursionError)가 발생했다. 이는 재귀함수가 너무 깊이 들어갈 경우 발생한다.
이땐 당황하지 말고 sys 모듈을 불러와 sys.setrecursionlimit(n) 을 적어주면 된다. 여기서 n은 최대 깊이를 의미한다.
sys.setrecursionlimit(10**4) 을 넣어줌으로써 런타임 에러를 해결했더니 시간초과가 나왔다..
생각해낸 알고리즘에는 문제가 없어보였기에 질문 검색 탭에 들어가서 질문들을 살피는 도중 pypy와 python 둘에 관한 정답판정 글을 보았다. 그래서 코드 수정없이 python을 pypy로 제출하였더니 정답판정 받았다..ㅎㅎ

이후 다른 코드를 살펴보니, 파이썬으로 정답판정 받은 코드들은 물의 위치를 매번 확인하는 것이 아니라 저장해두어서 시간을 절약하였다.

런타임 에러, 시간 초과 그리고 시간 초과 끝에 맞았습니다!!

 

📕 풀이

얼음인 곳을 찾고, 그 주위의 물의 갯수를 체크하여 얼음을 녹여주었다.
위 과정을 계속 반복하였는데, 반복할 때마다 빙산이 둘 이상으로 쪼개졌는지 BFS로 확인해주고, 쪼개졌다면 반복횟수를 출력한다.
그리고 빙산이 다 녹을 때까지 아직 빙산이 둘 이상으로 쪼개지지 않았다면, 현재 빙산은 전부 0이라는 의미이다. 이 경우도 체크하여 0을 출력해주면 되었다.

 

💻 코드

import sys 
sys.setrecursionlimit(10**4)
input = sys.stdin.readline

# 상하좌우로 얼음 살필 좌표
dx = [1,-1,0,0]
dy = [0,0,1,-1]

n,m = map(int,input().rstrip().split())
# 얼음과 물의 정보를 입력받는다.
ice = [list(map(int, input().rstrip().split())) for i in range(n)]
# 한번 녹은 빙산을 잠시 저장해줄 리스트
new = [[0 for i in range(m)] for i in range(n)]


# 빙산이 둘 이상으로 나누어졌는지 탐색하는 함수
def dfs(x,y):
    if x <= -1 or y <= -1 or x >= n or y >= m: 
        return False
    if ice[x][y] >0: # 바닷물이 아닌 빙산이라면
        ice[x][y] = 0 # 방문 처리
        # 상하좌우로 DFS 돌린다.
        dfs(x,y-1) 
        dfs(x,y+1)
        dfs(x+1,y)
        dfs(x-1,y)
        return True
    return False
    
year = 0 # 연도 카운트

while True:
    no = 0 # 둘 이상으로 쪼개지지 않고 전부 녹는 경우를 체크하기 위한 변수
    for i in range(n): 
        for j in range(m):
            if ice[i][j] > 0: # 얼음이라면
                cnt = 0
                for k in range(4):
                	# 상하좌우 네군데가 얼음인지 바닷물인지 체크
                    nx = i + dx[k]
                    ny = j + dy[k]

                    if nx <= -1 or ny <= -1 or nx >= n or ny >= m: # 벗어나는 경우 컨티뉴
                        continue

                    if ice[nx][ny] == 0: # 바닷물이라면 카운트 올려줌
                        cnt += 1
                # 이제 현재 빙산을 녹여준다.
                # if 문 사용한 이유는 음수가 되지 않게 하기 위해서
                if ice[i][j] - cnt >= 0:
                    new[i][j] = ice[i][j] - cnt
                else:
                    new[i][j] = 0
            else: # 바닷물이라면
                no += 1 # no 카운트를 올려주고
    # 전부 바닷물이라면 0 출력 후 종료
    if no == n*m: 
        print(0)
        break
	# 둘로 쪼개졌는지 체크하기 위해 DFS 함수를 호출한다.
    result = 0
    for i in range(n):
        for j in range(m):
            if dfs(i,j) == True:
                result += 1
    if result >= 2: # 둘 이상 쪼개졌다면 year 출력하고 종료
        print(year)
        break
    year += 1

	# 빙산 정보 업데이트
    ice = new
    new = [[0 for i in range(m)] for i in range(n)]

 

 

빙산

🔗 문제링크 : 빙산

2573번: 빙산