[백준/Python] 2573번(DFS,BFS)_빙산

📌문제 유형

DFS, BFS

 

📌문제

2573번: 빙산

 

📌나의 문제풀이

- 실패(DFS)

import sys
sys.setrecursionlimit(10**5)

n,m = map(int,input().split())

maps = []
for _ in range(n):
    a = list(map(int,input().split()))
    maps.append(a)


def dfs(x,y):
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    cnt = 0


    # x,y는 숫자가 있는 값이어야 함
    # 빙산 값 줄이기
    for i in range(4):
        nx = x + dx[i]
        ny  = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m :
            if visited[nx][ny] == 0 and maps[nx][ny] == 0:
                cnt += 1

    maps[x][y] -= cnt
    if maps[x][y] - cnt < 0:
        maps[x][y] = 0
    
    visited[x][y] = -1

    # 숫자 있는 곳으로 x,y 옮기기
    for j in range(4):
        nx1 = x + dx[j]
        ny1  = y + dy[j]

        if 0 <= nx1 < n and 0 <= ny1 < m :
            if visited[nx1][ny1] == 0 and maps[nx1][ny1] > 0:
                dfs(nx1,ny1)
  

# 빙산의 개수가 2개 이상으로 쪼개질 때까지 반복
# visited로 순회하기
# 빙산이 다 녹을때 분리되지 않으면 0
num = 0
while True:
    c = 0
    visited = [[0 for _ in range(m)] for _ in range(n)]

    # 숫자인 경우, 계산하고 dfs로 넘어가기
    # 한 번에 순회가 끝난경우 넘어가고, 두 번 이상 순회하는 경우 while문 종료
    for x_ in range(1, len(maps)-1):
        for y_ in range(1, len(maps[0])-1):
            if maps[x_][y_] > 0 and visited[x_][y_] == 0:  # 값이 0보다 크고, 방문하지 않은 경우
                c += 1
                dfs(x_,y_)

    if c > 1:
        break
    num += 1

    if maps == [[0 for _ in range(m)] for _ in range(n)]:
        num = 0
        break

print(num)

 

📌 다른사람의 문제풀이

- BFS

[백준] 2573번, 빙산 (Python)

import collections

n, m = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
queue = collections.deque()
day = 0
check = False

def bfs(a,b):
    queue.append((a,b))
    while queue:
        x,y = queue.popleft()
        visited[x][y] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] != 0 and visited[nx][ny] == False:	# 아직 순회하지 않은 곳 큐에 넣기
                    visited[nx][ny] = True
                    queue.append((nx,ny))
                elif graph[nx][ny] == 0:
                    count[x][y] += 1
    return 1

# 빙산이 분리될때까지 돌아줌
while True:
    visited = [[False]*m for _ in range(n)]
    count = [[0]*m for _ in range(n)]
    result = []
    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0 and visited[i][j] == False:
                result.append(bfs(i,j))
    # 빙산을 깍아줌           
    for i in range(n):
        for j in range(m):
            graph[i][j] -= count[i][j]
            if graph[i][j] < 0:
                graph[i][j] = 0
    
    if len(result) == 0: # 빙산이 다없어질때까지 분리가 되지않으면 break
        break
    if len(result) >= 2: # 빙산이 분리되면 break
        check = True
        break
    day += 1

if check:        
    print(day)
else:
    print(0)

- DFS

백준 2573 빙산 파이썬 (DFS)

import sys
sys.setrecursionlimit(10**5)
def dfs(i,j):#2가지 경우로 나뉘는걸 체크해주기 위한 함수.
    for k in range(4):
        nx = dx[k]+i
        ny = dy[k]+j
        if 0<=nx<n and 0<=ny<m and vist[nx][ny]:
            vist[nx][ny]=False
            if s[nx][ny]!=0:
                dfs(nx,ny)
            

input = sys.stdin.readline
n,m = map(int,input().split())
s=[list(map(int,input().split())) for _ in range(n)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
vist = [[False]*m for _ in range(n)]#방문 체크
t = 0

while True:
    t+=1
    for i in range(n):#빙하를 녹이는 함수
        for j in range(m):
            if s[i][j]!=0:
                vist[i][j] = True #앞서 말한 경우를 방지해주기 위한 작업
                c=s[i][j]
                for k in range(4):
                    nx = dx[k]+i
                    ny = dy[k]+j
                    if 0<=nx<n and 0<=ny<m and not vist[nx][ny]:
                        if s[nx][ny]==0:
                            c-=1
                            if c==0:#음수가 되면 안 되니 dfs작업을 멈춰준다.
                                break
                s[i][j]=c#녹은 빙하를 저장해줌
                
    ch=0#영역의 개수
    for i in range(n):
        for j in range(m):#방문체크 배열을 재사용하기 위해 True->False로 다 고쳐준다.
            if s[i][j]!=0 and vist[i][j]:
                dfs(i,j)#영역을 체크한다.
                ch+=1
            elif s[i][j]==0 and vist[i][j]:
                vist[i][j]=False
                
    if ch>=2:#영역이 2개 이상으로 나뉜경우니 출력해주고 반복문을 탈출한다.
        print(t)
        break
    elif ch==0:#한번에 녹았다는 의미이므로 0을 출력해주고 반복문을 탈출한다.
        print(0)
        break