Python3/백준 알고리즘
2022.04.09 [백준] (파이썬 python) 빙산
ian's coding
2022. 4. 9. 17:40
728x90
반응형
https://www.acmicpc.net/problem/2573
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
풀이
이 문제는 bfs를 이용하여 문제를 해결하였다.
문제에서 주어지는 빙산의 배열을 arr에 담고 bfs를 돌려 각 빙산이 몇개의 바다에 접해 있는지 체크하여 빙산의 위치에 해당하는 melt배열에 접해있는 수를 저장해 주었다. 바로 arr배열에서 빙산이 녹은 값을 업데이트해주지 않은 이유는 만약 빙산이 녹아 바다(0)이 되었을 때, 다음의 빙산에 영향을 주기 때문에 bfs를 모두 돌고 난 뒤, 한번에 빙산의 녹은 값을 업데이트 해주었다. 그리고 visit배열에 빙산의 방문여부를 체크하여 방문하지 않은 빙산만 들리게 하였다.
그리고 bfs를 돌때마다 cnt를 증가시켜 빙산의 덩어리 수를 체크했다. 만약 cnt이 2보다 크면 해당 day에 -1을 하여 출력하고 cnt이 0이면 모든 빙하가 녹았기 때문에 0을 출력했다.
여기서 day-1을 출력하는 이유는 하루가 지난 뒤의 빙하의 갯수를 세어 주었기 때문에 이전 날을 출력했다.
|
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
|
from collections import deque
n,m=map(int,input().split())
arr=[]
for _ in range(n):
arr.append(list(map(int,input().split())))
dxy=[(1,0),(-1,0),(0,1),(0,-1)]
def bfs(x,y,vis,melt):
deq=deque()
deq.append([x,y])
vis[x][y]=True
while deq:
x,y=deq.popleft()
for i in range(4):
nx = x + dxy[i][0]
ny = y + dxy[i][1]
if 0 <= nx < n and 0 <= ny < m:
if arr[nx][ny] == 0:
melt[x][y]-=1
elif not vis[nx][ny]:
vis[nx][ny]=True
deq.append([nx,ny])
day=0
cnt=0
while True:
vis = [[False for _ in range(m)] for _ in range(n)]
melt = [[0 for _ in range(m)] for _ in range(n)]
day+=1
ch=False
for i in range(n):
for j in range(m):
if arr[i][j]!=0 and not vis[i][j]:
ch=True
bfs(i,j,vis,melt)
cnt+=1
if cnt>=2:
print(day-1)
break
elif cnt==0:
print(0)
break
else:
cnt=0
for i in range(n):
for j in range(m):
arr[i][j]+=melt[i][j]
if arr[i][j]<0:
arr[i][j]=0
|
cs |
728x90
반응형