[백준] 2573 빙산

백준 2573번 빙산

구현 / 그래프 / 깊이우선탐색 / 너비우선탐색

 

 

 

[문제]

 

 

이또한 bfs문제이고 상하좌우를 비교했을 떄 값이 0인지 비교하면 됨

 

 

 

 

 

 

[과정]

 

3가지 스텝으로 진행하면 된다.

• 빙산이 두 덩어리이상으로 나누어졌는지 확인
• 빙산이 전부 녹았는데 두 덩어리로 나누어지지 않은 경우 확인
• 빙산 녹이기 

바깥에 while문을 하나 돌리고 위의 3과정을 순서대로 진행하면서 두 덩어리이상으로 나누어졌을시 반복문을 끝내면 된다.

 

코드를 보면 알겠지만 빙산을 두 덩어리로 나눈 경우에 bfs를 사용했는데

똑같은 코드를 빙산녹이기에 사용해서 코드가 중복되었다.

 

※ 주의

빙산 녹이기 부분에서 하나의 좌표에서 상하좌우를 비교해서 녹일때마다 바다를 만나면 만나는 개수를 세서 해당 좌표값을 줄여주어야 한다.

하지만 큐를 돌릴때마다 즉시 갱신해버리면 다른 빙산에서 상하좌우를 비교할 때 다른곳이 바다로 바뀌어 버렸기에 잘못된 값으로 갱신될 수 있다.

따라서 별도의 변수에 바다가 되는 좌표값을 넣어놓고 큐를 한번 전체 돌릴때 바다가 되는 좌표는 '-1'과 같은 0이하의 수나 다른 문자로 치환해서 저장해놓는다. 이후에 해당 변수속의 좌표값을 바다(0)로 돌려주면 된다.

 

나의 경우에는 '-1'로 치환후에 1세트 반복이 끝나면 바다(0)으로 다시 바꾸어 주었다.

 

 

 

[소스코드]

 

# 빙산

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

# 입력
n,m = map(int, input().split())
arr = []
for _ in range(n):
    tmp = list(map(int, input().split()))
    arr.append(tmp)

# 빙산의 위치 찾기 
iceberg = []
for i in range(n):
    for j in range(m):
        if arr[i][j] != 0:
            iceberg.append([i,j])

dx = [-1,1,0,0]
dy = [0,0,-1,1]

q = deque(iceberg)
melt_q = deque()

result = 0
result_cnt = 0
while True:
    # step1) 빙산이 두 덩어리로 분리되었는지 확인
    count = 0
    visited = [[False]*m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            if arr[i][j] != 0 and visited[i][j] == False:
                melt_q.append([i,j])
                while melt_q:
                    data = melt_q.popleft()

                    x = data[0]
                    y = data[1]
                    visited[x][y] = True
                    count += 1
                    
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if 0 <= nx < n and 0 <= ny < m:
                            if arr[nx][ny] != 0 and visited[nx][ny] == False:
                                visited[nx][ny] = True
                                melt_q.append([nx,ny])
                  
                if len(q) != count:
                    result_cnt = 1
                    break
        if result_cnt == 1:
            break
    if result_cnt == 1:
        print(result)
        break

    # step2) 전부 녹았는데 두 덩어리로 분리되지 않았을 경우
    melted = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 0:
                melted += 1
    if melted == n*m:
        print(0)
        break
    
    # step3) 빙산 녹이기
    melted_iceberg = []    # 녹은 빙산 
    for t in range(len(q)):
        data = q.popleft()
        x = data[0]
        y = data[1]
        
        cnt = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if arr[nx][ny] == 0:
                cnt += 1
                
        arr[x][y] -= cnt
        if arr[x][y] <= 0:
            arr[x][y] = -1
            melted_iceberg.append([x,y])
        else:
            q.append([x,y])
        
    # step4) 녹은 빙산을 0으로 바꾸어 주기
    for melted in melted_iceberg:
        mx,my = melted
        arr[mx][my] = 0
    result += 1

 

소스코드가 많이 중첩됬고 쓸모없는 부분이 많다... 역대급인것 같다.

짜면서도 '너무 길다.. 이거 분명 압축가능한데..ㅠㅠ' 하면서 풀었다. 1시간 반정도 걸렸다.

압축하면 반절로 압축될 것 같다.

이후에 간결한 코드로 변환해보도록 하자ㅠㅠ

---

 

[통과]

 

파이썬으로 제출시 시간초과가 남

파이파이로 제출해야 통과가 됨

반절짜리 정답이라고 봐도 될 듯ㅎㅎ

 

이제 골드3~4문제는 평균 1시간반정도 걸리는 듯 하다.

30분이내로 풀 수 있어야 코테를 통과한다고 하니 좀더 익숙해져보자