💻 알고리즘/백준

[ 백준 ] 2573 빙산 (python)

졔링 2022. 6. 7. 00:03
728x90

 

 

 

 

 

 

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 = [001-1]
dy = [1-100]
 
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

 

 

 

 

728x90