[ 백준 ] 2573 빙산 (python)
https://www.acmicpc.net/problem/2573
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
🔥 문제 풀이
✔ 처음 접근 방법
- 값이 0인 바다로 BFS를 실행해서 바다 근처에 빙산이 존재한다면 빙산의 값에 -1 을 하도록 구현함
❗ 값이 2이면서 주변에 두개의 바다와 닿아있다면 0이 된다. 그 이후에 BFS를 이어서 실행하면 빙산이 사라진 이곳 조차도 바다로 인식해서 결과 값이 다르게 나옴 -> deepcopy를 사용해서 해결해줌
- 1년이 지난 후 빙산의 조각이 줄어들었다면, DFS를 사용해서 빙산이 몇 덩어리 인지 count 하도록 구현함
- 이 과정을 빙산이 아예 없거나, 빙산 조각이 2개 이상일 때 까지 반복해준다.
이 과정 속에서 for문을 자주 사용해서 그런지 예제는 통과했지만 시간초과가 발생했다..😥
✔ 정답 풀이 접근 방법
- 위에서 시간초과가 났던 상황과는 다르게 빙산을 기준으로 BFS를 실행시켜준다.
❗ zero list를 만들어서 빙산을 기준으로 BFS실행 중 바다를 만나면 zero에 값을 +1 해준다.
❗ BFS 실행 결과를 res list에 담아준다 -> res의 길이를 확인해서 빙산이 존재하는지 유무를 확인하기 위함 -> DFS 실행할 필요 없어짐
- BFS실행을 완료하면 for문을 한번 더 실행해서 arr 값에서 zero 리스트에 들은 값만큼 빙산을 줄여준다
❗ 바다에 닿은 빙산을 줄여주는 과정을 BFS 끝난 후에 진행하기 때문에 따로 deepcopy를 사용해주지 않아도 된다.
- 이 과정을 빙산이 아예 없거나, 빙산 조각이 2개 이상일 때까지 반복해준다.
이렇게 문제를 풀어주면 시간초과 없이 pypy로 문제없이 잘 통과한다😎
BFS 실행 결과를 리스트에 담아서 다시 For문을 돌려 빙산의 개수를 확인해 주지 않아도
리스트의 길이를 통해 빙산의 개수를 알 수 있도록 구현하는 방법은 생각하지 못했었는데 다음번에 비슷한 문제를 접하게 되면 이 방법 꼭 사용해봐야지😁
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
from collections import deque
import sys
input = sys.stdin.readline
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
queue = deque()
year = 0
flag = False
def bfs(x, y):
queue.append((x, y))
visited[x][y] = True
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if arr[nx][ny] != 0 and not visited[nx][ny]:
visited[nx][ny] = True
queue.append((nx, ny))
# 근접한 부분에 바다가 있다면,
# 현재 위치인 (x, y)좌표에서 zero 리스트에 값을 추가해준다
# (나중에 arr[x][y]에서 zero[x][y] 만큼 빼주기 위해서)
elif arr[nx][ny] == 0:
zero[x][y] += 1
return 1
while True:
visited = [[False] * m for _ in range(n)]
zero = [[0] * m for _ in range(n)]
res = []
# 빙산이 바다와 닿아있는 면적 구하기
# res에 값을 append해서 몇개의 빙산 덩어리인지 확인 가능
for i in range(n):
for j in range(m):
if arr[i][j] != 0 and not visited[i][j]:
res.append(bfs(i, j))
# 바다에 닿은 면적 만큼 빙산 줄이기
for i in range(n):
for j in range(m):
arr[i][j] -= zero[i][j]
if arr[i][j] < 0:
arr[i][j] = 0
# 빙산이 존재하지 않는다면
if len(res) == 0:
print(0)
break
# 빙산이 2개이상 존재한다면
if len(res) >= 2:
print(year)
break
year += 1
|
cs |