문제
지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.
그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보
| 2 | 4 | 5 | 3 | |||
| 3 | 2 | 5 | 2 | |||
| 7 | 6 | 2 | 4 | |||
빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일 년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일 년 후에 그림 2와 같이 변형된다.
그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.
그림 2
| 2 | 4 | 1 | ||||
| 1 | 1 | 5 | ||||
| 5 | 4 | 1 | 2 | |||
그림 3
| 3 | ||||||
| 4 | ||||||
| 3 | 2 | |||||
한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
입력
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.
출력
첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.
예제 입력 1
5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0예제 출력 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 += 11) 빙산의 좌표를 모두 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))
문제 출처
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
'[Python] Baekjoon > Graph(그래프)' 카테고리의 다른 글
| [백준(Baekjoon)] 2206 벽 부수고 이동하기 (0) | 2021.12.08 |
|---|---|
| [백준(Baekjoon)] 4963 섬의 개수 (0) | 2021.12.08 |
| [백준(Baekjoon)] 11724 연결 요소의 개수 (0) | 2021.11.18 |
| [백준(Baekjoon)] 2606 바이러스 (0) | 2021.11.14 |
| [백준(Baekjoon)] 1260 DFS와 BFS (0) | 2021.11.09 |
댓글