[Python] 백준 / gold / 2573 : 빙산
문제 링크 : https://www.acmicpc.net/problem/2573
DFS / BFS 문제이다. BFS 보다 DFS 에 자신이 없었기 때문에 연습하려고 DFS로 풀었다. 로직은 잘 구현한 것 같은데, recursion error, type error, time limit, memory limit 아주 난리가 났다..
그래서 파이썬 메모리 관련 공부하던 중에 파이썬은 변수도 객체처럼 메모리를 할당한다는 것을 알게 되었다. 하여튼 다시 BFS로 풀었고 앞으로도 두 가지 풀이가 가능한 문제라면 BFS로 푸는게 안전할 것 같다.
파이썬 정답 코드
import sys from collections import deque direction = [(-1,0), (1,0), (0,-1), (0,1)] N, M = map(int, sys.stdin.readline().split()) graph = [] visit = [[False]*M for _ in range(N)] melt = [[0]*M for _ in range(N)] for _ in range(N): graph.append(list(map(int, sys.stdin.readline().split()))) year = 0 while True: # print('current situation') # for x in graph: # print(x) # 초기화 for i in range(N): for j in range(M): visit[i][j] = False melt[i][j] = 0 # 빙산 개수 탐색 ice = 0 for i in range(N): for j in range(M): if not visit[i][j] and graph[i][j] > 0: #print('bfs start',i,j) q = deque() q.append((i,j)) visit[i][j] = True while q: x, y = q.popleft() ocean = 0 for d in direction: nx = x + d[0] ny = y + d[1] if 0<=nx<N and 0<=ny<M: if graph[nx][ny] <= 0: ocean += 1 if not visit[nx][ny] and graph[nx][ny] > 0: q.append((nx,ny)) #print('append',nx,ny) visit[nx][ny] = True melt[x][y] = ocean ice += 1 # 종료 조건 if ice >= 2: print(year) break elif ice == 0: print(0) break #print('year ice',year,ice) # 빙산 녹이기 for i in range(N): for j in range(M): graph[i][j] -= melt[i][j] if graph[i][j] < 0: graph[i][j] = 0 year += 1
Author And Source
이 문제에 관하여([Python] 백준 / gold / 2573 : 빙산), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@heyksw/Python-백준-gold-2573-빙산저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)