on
[백준(Baekjoon)] 2573 빙산
[백준(Baekjoon)] 2573 빙산
예제 입력 1
예제 출력 1 2
나의 코드
[Python(파이썬)]
코드 1 (pypy3 통과, python3 시간초과)
def bfs(x, y, visited): q = deque([[x, y]]) # 시작 좌표 visited[x][y] = 1 # 시작 좌표 노드 방문 표시 while q: # 큐가 빌 때까지 x, y = q.popleft() zerocnt = 0 # 동서남북에 0이 저장된 칸의 개수 for i in range(4): # 상하좌우 이동-> 4번 nx, ny = x + dx[i], y + dy[i] if n > nx >= 0 and m > ny >= 0: if graph[nx][ny] > 0 and visited[nx][ny] == 0: visited[nx][ny] = 1 q.append([nx, ny]) if graph[nx][ny] <= 0: zerocnt += 1 if zerocnt != 0: meltinfo.append([x, y, zerocnt]) def iceberg(): # 빙산 카운트 함수 global result while True: cnt = 0 # 빙산의 개수 visited = [[0] * m for _ in range(n)] for j in range(1, n-1): # 첫번째, 마지막 행과 열의 항상 0 for k in range(1, m-1): if visited[j][k] == 0 and graph[j][k] > 0: cnt += 1 if cnt >= 2: # 빙산이 두 덩어리 이상 분리 된 경우 return result # 최초의 시간 출력 bfs(j, k, visited) while meltinfo: # 빙산 높이 변경 i1, i2, i3 = meltinfo.popleft() graph[i1][i2] -= i3 if cnt == 0: # 빙산이 두 덩어리 이상 분리 되기 전에 다 녹아버린 경우 return 0 result += 1 # 빙산이 한 덩이리 인 경우이기 때문에 1년 증가 import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우 이동변수 graph = [[*map(int, input().split())] for _ in range(n)] result = 0 # result: 빙산이 분리되는 최초의 시간 meltinfo = deque([]) # 빙산 녹는 위치, 정도 정보 저장 print(iceberg())
코드 2 (pypy3 통과, python3 통과)
def bfs(): visited = [[0] * m for _ in range(n)] q = deque() q.append(iceberg[0]) # 시작 좌표 visited[q[0][0]][q[0][1]] = 1 # 시작 좌표 노드 방문 표시 cnt = 0 # 이어진 빙산의 개수 while q: # 큐가 빌 때까지 x, y = q.popleft() cnt += 1 zerocnt = 0 # 상하좌우에 0이 저장된 칸의 개수 for i in range(4): # 상하좌우 이동-> 4번 nx, ny = x + dx[i], y + dy[i] if n > nx >= 0 and m > ny >= 0: if graph[nx][ny] > 0 and visited[nx][ny] == 0: visited[nx][ny] = 1 q.append((nx, ny)) if graph[nx][ny] <= 0: zerocnt += 1 if zerocnt != 0: meltinfo.append((x, y, zerocnt)) while meltinfo: # 빙산 높이 변경 i1, i2, i3 = meltinfo.popleft() graph[i1][i2] -= i3 if graph[i1][i2] <= 0 and (i1, i2) in iceberg: iceberg.remove((i1, i2)) return cnt import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우 이동변수 graph = [[*map(int, input().split())] for _ in range(n)] result = 0 # result: 빙산이 분리되는 최초의 시간 meltinfo = deque([]) # 빙산 녹는 위치, 정도 정보 저장 iceberg = [] # 빙산 for i in range(1, n-1): for j in range(1, m-1): if graph[i][j] != 0: iceberg.append((i, j)) while True: if len(iceberg) != bfs(): # 전체 빙산 개수와 시작 빙산과 이어져있는 빙산 개수 비교 print(result) # 두 덩어리 이상인 경우 출력 break result += 1 if sum(map(sum, graph[1:-1])) == 0: print(0) break
※ DFS구현
BFS하다가 계속 시간초과 나와서 혹시나 하고 DFS로도 구현해봤지만 pypy3 메모리초과, python3 시간초과 나와서 바로 다시 BFS로 되돌아갔다.
※ dfs 사용해보기 def dfs(x, y, visited): visited[x][y] = 1 # 시작 좌표 노드 방문 표시 zerocnt = 0 # 동서남북에 0이 저장된 칸의 개수 for i in range(4): # 상하좌우 이동-> 4번 nx, ny = x + dx[i], y + dy[i] if n > nx >= 0 and m > ny >= 0: if graph[nx][ny] > 0 and visited[nx][ny] == 0: visited[nx][ny] = 1 dfs(nx, ny, visited) if graph[nx][ny] <= 0: zerocnt += 1 if zerocnt != 0: meltinfo.append([x, y, zerocnt])
코드 풀이
이 문제는 '시간 초과'를 해결하는 것이 어려웠다.
pypy3는 통과가 되는데 Python3는 시간 초과가 나와서 통과하기 위해서 도대체 몇 번을 시도해봤는지,,,
python3을 통과하기 위해서 계속 수정해가며 pypy3 실행 시간을 7~800ms에서 468ms까지 줄였지만 python3는 끝까지 시간 초과가 나왔다.
결국 python3을 통과한 코드(코드 2)는 다른 사람의 코드에서 힌트를 얻어 해결했다.
코드 1 풀이 (pypy3 통과, python3 시간 초과)
제일 처음 구현한 코드 (pypy3 - 768ms)
def bfs(x, y): dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우 이동변수 graph = [item[:] for item in meltgraph] # 녹기 전 높이 정보 저장 q = deque([[x, y]]) # 시작 좌표 visited[x][y] = True # 시작 좌표 노드 방문 표시 while q: # 큐가 빌 때까지 x, y = q.popleft() bfscnt = 0 # 동서남북에 0이 저장된 칸의 개수 for i in range(4): # 상하좌우 이동-> 4번 nx, ny = x + dx[i], y + dy[i] if n > nx >= 0 and m > ny >= 0: if graph[nx][ny] > 0 and visited[nx][ny] == False: q.append([nx, ny]) if graph[nx][ny] <= 0: bfscnt += 1 visited[nx][ny] = True meltgraph[x][y] -= bfscnt import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) meltgraph = [[*map(int, input().split())] for _ in range(n)] result = 0 # result: 빙산이 분리되는 최초의 시간 while True: cnt = 0 # 빙산의 개수 visited = [[False]*m for _ in range(n)] for j in range(n): for k in range(m): if visited[j][k] == False and meltgraph[j][k] > 0: cnt += 1 bfs(j, k) else: visited[j][k] = True if cnt == 0: # 빙산이 두 덩어리 이상분리 되기 전에 다 녹아버린 경우 print(0) break elif cnt >= 2: # 빙산이 두 덩어리 이상 분리 된 경우 print(result) # 최초의 시간 출력 break result += 1 # 1년 증가
제일 처음 위와 같이 구현했을 때 실행 시간이 768ms가 나왔다. 따라서 위의 코드를 코드 1(468ms)까지 줄이기 위해서
크게 아래 4가지를 수정하였다.
1. 이중 for문 1~n-1, 1~m-1만 실행하기
2. 빙산이 두 덩어리 이상 분리된 경우
3. 1년 뒤 빙산이 녹고 난 후 그래프
4. 일반 리스트 대신 deque 이용하기
1. 이중 for문 1~n-1, 1~m-1만 실행하기
'배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.'라는 조건이 문제에 제시되어있다.
따라서 이중 for문을 0~n, 0~m까지 하지 않고 테두리 부분은 모두 0이므로 1~n-1, 1~m-1까지만 실행하면 된다.
수정 전
for j in range(n): for k in range(m):
수정 후
for j in range(1, n-1): # 첫번째, 마지막 행과 열은 항상 0 for k in range(1, m-1):
2. 빙산이 두 덩어리 이상 분리된 경우
문제에서 원하는 결과값은 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)이다.
따라서 빙산이 두 덩어리 이상 분리된 경우 (bfs 함수가 두 번 호출될 상황 발생 시) 더 이상 실행하지 않고 바로 return 하면 된다.
수정 전
if visited[j][k] == False and meltgraph[j][k] > 0: cnt += 1 bfs(j, k)
수정 후
if visited[j][k] == 0 and graph[j][k] > 0: cnt += 1 if cnt >= 2: # 빙산이 두 덩어리 이상 분리 된 경우 return result # 최초의 시간 출력 bfs(j, k, visited)
3. 1년 뒤 빙산이 녹고 난 후 그래프
※ 빙산이 녹을 때 주의해야 할 점
빙산은 위와 같이 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다.
하지만 아래와 같이 2가 0으로 변했다고 해서 4가 녹을 때 2가 0으로 변한 자리까지 계산해서 녹아서는 안된다.
틀린 그림!!!
순서대로 녹는 것이 아니라 빙산은 동시에 녹아야 한다.
맞게 녹은 빙산
수정 전
1) 처음엔 빙산의 높이를 나타내는 그래프를 두 개 만든다.
graph = [item[:] for item in meltgraph] # 녹기 전 그래프를 두 개의 리스트로 만든 다음
2) 동서남북에 0이 있는지는 graph 리스트로 비교하고 0의 개수만큼 meltgraph에서 뺀다.
if graph[nx][ny] > 0 and visited[nx][ny] == False: q.append([nx, ny]) if graph[nx][ny] <= 0: bfscnt += 1 meltgraph[x][y] -= bfscnt # 녹을 때마다 meltgraph에 저장
3) bfs가 호출되면 다시 녹은 빙산의 높이가 저장되어있는 meltgraph의 데이터 값을 graph에 담는다.
위와 같이 1~3)을 실행하면 bfs를 실행할 때마다 이중 for문을 이용해 n*m 리스트를 생성해야 하고 계속해서 meltgraph의 값에 접근해야 한다.
불필요한 접근을 줄이기 위해 빙산 녹는 위치와 정도 정보를 저장하는 meltinfo를 만들어 모든 빙산에 방문한 뒤 meltinfo의 길이만큼만 실행하여 수정해주면 실행 시간이 줄어든다.
수정 후
# bfs 함수 meltinfo = deque([]) # 빙산 녹는 위치, 정도 정보 저장 if zerocnt != 0: meltinfo.append([x, y, zerocnt]) # iceberg 함수 (모든 빙산에 방문한 뒤 실행) while meltinfo: # 빙산 높이 변경 i1, i2, i3 = meltinfo.popleft() graph[i1][i2] -= i3
4. list 대신 deque 이용하기
from collections import deque q = deque([[x, y]])
list의 경우 값을 꺼낼 때, O(N)의 시간 복잡도는 가지지만 deque는 dict과 같은 O(1) 시간 복잡도를 가진다.
코드 2 풀이 (pypy3 통과, python3 통과)
코드 1과 다른 점은 두 덩어리 이상으로 분리되는지 확인하는 부분이다.
코드 1은 좌표 (1, 1)부터 시작하여 이중 포문을 이용해 순서대로 이동해 방문했는지, 빙산이 있는지 확인해가며 빙산이 총 몇 부분인가 확인한다면
코드 2는 전체 빙산의 개수를 구한 다음 빙산의 첫 번째 좌표에서 이어져있는 빙산의 개수와 비교한다.
for i in range(1, n-1): for j in range(1, m-1): if graph[i][j] != 0: iceberg.append((i, j)) while True: if len(iceberg) != bfs(): # 전체 빙산 개수와 시작 빙산과 이어져있는 빙산 개수 비교 print(result) # 두 덩어리 이상인 경우 출력 break result += 1
1) 빙산의 좌표를 모두 iceberg에 담는다.
2) 첫 번째 빙산의 좌표(iceberg[0])부터 bfs를 실행한다. -> 첫번째 빙산과 연결되어있는 빙산의 개수를 반환
q.append(iceberg[0]) # 시작 좌표
3) iceberg의 길이(빙산이 녹기 전)와 bfs에서 반환된 값을 비교한다.
if len(iceberg) != bfs(): # 전체 빙산 개수와 시작 빙산과 이어져있는 빙산 개수 비교
3-1) 같다면 result 1 증가 (빙산이 한 덩어리로 되어있다는 의미)
3-2) 다르다면 현재 result 값 출력 (빙산이 두 덩어리 이상으로 나누어져 있다는 의미)
※ 2)에서 bfs 실행할 때 빙산이 녹아 0이 되었다면 iceberg에서 해당 좌표 제거 -> len(iceberg)는 1년이 지난 후 계속 바뀐다.
while meltinfo: # 빙산 높이 변경 i1, i2, i3 = meltinfo.popleft() graph[i1][i2] -= i3 if graph[i1][i2] <= 0 and (i1, i2) in iceberg: iceberg.remove((i1, i2))
문제 출처
from http://young-library.tistory.com/161 by ccl(A) rewrite - 2021-11-29 02:27:29