[파이썬] 백준 2573 : 빙산 (골드4)

[파이썬] 백준 2573 : 빙산 (골드4)

2573번: 빙산

---

문제

---

풀이

 

0. 방향성 생각

주어진 배열의 크기가 크고 시간이 지남에 따라 지속적으로 빙산의 개수를 체크해야한다.

DFS보다는 BFS가 시간적으로 이득일 것 같다.

또한 빙산에 인접한 바다의 개수를 세면서 빙산을 녹이면 빙산이 0이 될 경우에 오류가 발생할 수 있어서 추가적인 리스트를 만들어준다.

1. 입력받기

from collections import deque
import sys
input = sys.stdin.readline

h,w = map(int,input().split())
arr = []
for i in range(h):
    arr.append(list(map(int,input().split())))

 

2. BFS 함수 작성

step = [[1,-1,0,0],[0,0,1,-1]]
def bfs(x,y):
    q = deque()
    q.append((x,y))
    visit[y][x] = True
    while q:
        x,y = q.popleft()
        if 0<=x<w and 0<=y<h :
            for d in range(4):
                nx = x + step[0][d]
                ny = y + step[1][d]

                if 0<=nx<w and 0<=ny<h :
                    if arr[ny][nx] != 0 and not visit[ny][nx]:
                        visit[ny][nx] = True
                        q.append((nx,ny))

 

3. 빙산 개수 세기

year = 0
while True:
    # 1)
    visit = [[False]*w for i in range(h)]
    ice = 0
    for i in range(h):
        for j in range(w):
            if arr[i][j] != 0 and not visit[i][j]:
                visit[i][j] = True
                bfs(j,i)
                ice += 1
    
    if ice >= 2 :
        print(year)
        break
    else :
        year += 1
        if ice == 0:
            print(0)
            break
            
    # 2)
    sea = [[0]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            if arr[i][j] != 0 :
                count = 0
                for d in range(4):
                    nx = j + step[0][d]
                    ny = i + step[1][d]
                    if 0<=nx<w and 0<=ny<h and arr[ny][nx]==0:
                        count += 1
                sea[i][j] = count
                
    # 3)            
    for i in range(h):
        arr[i] = list(map(lambda x,y: x-y if x>y else 0,arr[i],sea[i]))

1. 먼저 주어진 배열에 대해서 BFS를 수행해서 빙산의 개수를 카운트한다. 이후 빙산의 개수가 2개 이상이면 걸린 시간을 출력하고 탈출. 아닌 경우에는 시간을 늘린다. 시간은 느는데 빙산이 계속 한덩이다가 녹는 경우는 0을 출력하고 탈출한다.
2. 인접한 바다의 개수를 넣을 리스트인 sea를 초기화시키고 2중 for문을 돌며 빙산마다 인접한 빙산 수를 계산한다
3. 빙산의 높이 - 인접한 바다의 칸수를 계산한다.

 

 

---

전체코드

from collections import deque
import sys
input = sys.stdin.readline

h,w = map(int,input().split())
arr = []
for i in range(h):
    arr.append(list(map(int,input().split())))

step = [[1,-1,0,0],[0,0,1,-1]]
def bfs(x,y):
    q = deque()
    q.append((x,y))
    visit[y][x] = True
    while q:
        x,y = q.popleft()
        if 0<=x<w and 0<=y<h :
            for d in range(4):
                nx = x + step[0][d]
                ny = y + step[1][d]

                if 0<=nx<w and 0<=ny<h :
                    if arr[ny][nx] != 0 and not visit[ny][nx]:
                        visit[ny][nx] = True
                        q.append((nx,ny))
                        
year = 0
while True:
    visit = [[False]*w for i in range(h)]
    ice = 0
    for i in range(h):
        for j in range(w):
            if arr[i][j] != 0 and not visit[i][j]:
                visit[i][j] = True
                bfs(j,i)
                ice += 1
    
    if ice >= 2 :
        print(year)
        break
    else :
        year += 1
        if ice == 0:
            print(0)
            break

    sea = [[0]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            if arr[i][j] != 0 :
                count = 0
                for d in range(4):
                    nx = j + step[0][d]
                    ny = i + step[1][d]
                    if 0<=nx<w and 0<=ny<h and arr[ny][nx]==0:
                        count += 1
                sea[i][j] = count
                
    for i in range(h):
        arr[i] = list(map(lambda x,y: x-y if x>y else 0,arr[i],sea[i]))

34%에서 python3로는 시간초과해서 pypy3로 풀었습니다.