[백준 파이썬] 2573 빙산

[백준 파이썬] 2573 빙산

https://www.acmicpc.net/problem/2573

2573번: 빙산

 

문제

입력

첫 줄에는 이차월 배열의 행의 개수와 열의 개수를 나태 내는 N M 이 주어진다

두 번째 줄부터  배열의 각 행을 나타내면 M개의 정수가 비칸 사이에 주어진다 

간 칸은 0이상 10 이하의 값이 들어간다 

첫 번째 행과 열 마지막행과 열에는 항상 0으로 채워진다 

출력

첫줄에 빙산이 분리되는 최초의 시간을 출력한다 

빙산이 다 녹음 때 까지 분리되지 않으면 0을 출력한다.

풀이

빙산이 있고 주변에 바다가 있으면 바다 주변에 있는 바다 수만큼 빙산의 값이 -1씩 내려간다 

0이 되고 난 후에는 주변의 다른 빙산의 영향을 주면 안되기에 이부분을 생각해야한다 

그리고 이렇게 한번 다 돌고 난후 빙산이 서로 연결되어 있는지 아닌지 확인해야 한다

 

일단 난 첫 번째로 생각한 거는 BFS로 빙산의 값을 감소시키고 그 후 DFS를 돌려 빙산이 나눠졌는지 확인하려고 했다

파이썬에서는 안 돌아갔지만 pypy3에서는 돌아갔다.

 

첫 번째 방식의 BFS 코드 

while q:
    x,y,count=q.popleft()
    if count!=day:
        day+=1
        vi=[[False for _ in range(k)] for _ in range(n)]

        cnt=0

        for i in range(n):
            for j in range(k):
                if not vi[i][j] and graph[i][j]!=0:
                    dfs(i,j)
                    cnt+=1
        vi=[[False for _ in range(k)] for _ in range(n)]

    if cnt>=2:
        print(day)
        break

    
    if vi[x][y]!=True and graph[x][y]!=0:
        vi[x][y]=True

        for p in range(4):
            x1=x+ix[p]
            y2=y+iy[p]
            if 0<= x1 <n and 0<=y2<k and graph[x1][y2] ==0 and vi[x1][y2]==False:
                graph[x][y]-=1
        if graph[x][y] <0:
            graph[x][y]=0
        q.append([x,y,count+1])

BFS을 돌릴 큐에 빙산들의 좌표와 현재 몇 번째 BFS를 돌리고 있는지 확인하기 위한 count를 함께 넣는다

만약 count와 현재 몇 년인지 값을 나타내는 day와 다를 경우 한 바퀴 다 돌았다고 판단하여 

DFS를 실행하여 빙산이 몇 개로 분리되었는지 확인한다 또한 방문 처리할 것도 다시 원래 상태로 될 돌려 다음 빙산의 값을 감소시킬 수 있도록 준비하고 day의 값을 +1 증가시킨다.

 

BFS 상하좌우를 확 하여 주변이 바다이면 현재 빙산값을 -1씩 해준다 

여기서 상하좌우를 확인할 때 그 값이 배열 범위 안의 값이어야 하고 배열값이 0 이어야 하며 그리고 

방문하지 않아야 한다 왜냐하면 방문 처리 되어있을 경우 이미 앞에서 빙산의 값을 감소시키고 온 것이라 그 빙산의 값이 0이 되어있을 수 있으므로 영향을 주지 않기 위해 방문하지 않은 것들만 확인한다.

 

 

두 번째 방법으로는 bfs만을 이용한 방법으로 

def bfs(x,y):
    q=deque([(x,y)])
    vi[x][y]=True
    while q:
        x1,y1=q.popleft()
        for p in range(4):
            x2=x1+ix[p]
            y2=y1+iy[p]
            if 0<= x2 <n and 0<=y2<k and graph[x2][y2] ==0 and vi[x2][y2]==False:
                graph[x1][y1]-=1
            elif  0<= x2 <n and 0<=y2<k and graph[x2][y2] !=0 and vi[x2][y2]==False:
                q.append((x2,y2))
                vi[x2][y2]=True
        if graph[x1][y1] <0:
            graph[x1][y1]=0

bfs코드 자체는 처음코드가 bfs 코드와 유사하다 

차이점은 dfs 부분이 빠지고 빙산 주변의 바다의 탐색하는 코드 아래에  주변에 빙산이 있을 경우 q에 집어넣는 코드가 추가되었다 집어넣으면서 탐색된 빙산은 방문처리한다 

이렇게 하면 bfs를 여러 번 시행할 때 시행한 횟수가 분리된 빙산의 덩어리가 된다.

 

while data:
    data2=[]
    vi=[[False for _ in range(k)] for _ in range(n)]

    count=0
    for i,j in data:
        if graph[i][j]!=0 and not vi[i][j]:
            bfs(i,j)
            count+=1
        if graph[i][j]==0:
            data2.append((i,j))


    day+=1


    if count>=2:
        print(day-1)
        break
    data = sorted(list(set(data) - set(data2)))

 

data 리스트에는 처음 빙산의 위치 좌표값들이 들어가고

data2에는 bfs 돌고 난 후 현재 0이 된 빙산의 좌표값들이 들어간다

data = sorted(list(set(data) - set(data2)))  하여 data에는 값이 0도인 좌표를 빼주면서 while문을 돌린다

 

코드

pypy3 전체 코드

from collections import deque
import sys
sys.setrecursionlimit(10**4)

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

graph=[list(map(int,input().split())) for _ in range(n)]

ix=[0,0,-1,1]
iy=[1,-1,0,0]

q=deque()

for i in range(n):
    for j in range(k):
        if graph[i][j]!=0:
            q.append([i,j,0])

day=0
vi=[[False for _ in range(k)] for _ in range(n)]

cnt=0
def dfs(x,y):
    vi[x][y]=True
    for p in range(4):
        x1=x+ix[p]
        y2=y+iy[p]
        if 0<= x1 <n and 0<=y2<k and graph[x1][y2] !=0 and vi[x1][y2]==False:
            dfs(x1,y2)
while q:
    x,y,count=q.popleft()
    if count!=day:
        day+=1
        vi=[[False for _ in range(k)] for _ in range(n)]

        cnt=0

        for i in range(n):
            for j in range(k):
                if not vi[i][j] and graph[i][j]!=0:
                    dfs(i,j)
                    cnt+=1
        vi=[[False for _ in range(k)] for _ in range(n)]

    if cnt>=2:
        print(day)
        break

    
    if vi[x][y]!=True and graph[x][y]!=0:
        vi[x][y]=True

        for p in range(4):
            x1=x+ix[p]
            y2=y+iy[p]
            if 0<= x1 <n and 0<=y2<k and graph[x1][y2] ==0 and vi[x1][y2]==False:
                graph[x][y]-=1
        if graph[x][y] <0:
            graph[x][y]=0
        q.append([x,y,count+1])
if cnt<2:
    print(0)

 

Python3 코드

from collections import deque
import sys
sys.setrecursionlimit(10**6)

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

graph=[list(map(int,input().split())) for _ in range(n)]

ix=[0,0,-1,1]
iy=[1,-1,0,0]



def bfs(x,y):
    q=deque([(x,y)])
    vi[x][y]=True
    while q:
        x1,y1=q.popleft()
        for p in range(4):
            x2=x1+ix[p]
            y2=y1+iy[p]
            if 0<= x2 <n and 0<=y2<k and graph[x2][y2] ==0 and vi[x2][y2]==False:
                graph[x1][y1]-=1
            elif  0<= x2 <n and 0<=y2<k and graph[x2][y2] !=0 and vi[x2][y2]==False:
                q.append((x2,y2))
                vi[x2][y2]=True
        if graph[x1][y1] <0:
            graph[x1][y1]=0


data=[]

for i in range(n):
    for j in range(k):
        if graph[i][j]!=0:
            data.append((i,j))

day=0
while data:
    data2=[]
    vi=[[False for _ in range(k)] for _ in range(n)]

    count=0
    for i,j in data:
        if graph[i][j]!=0 and not vi[i][j]:
            bfs(i,j)
            count+=1
        if graph[i][j]==0:
            data2.append((i,j))


    day+=1


    if count>=2:
        print(day-1)
        break
    data = sorted(list(set(data) - set(data2)))


if count<2:
    print(0)