[백준] 2573 파이썬(python) : 빙산 - (★)

2573번: 빙산

 

 

import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]
year = 0
check = False
q = deque()

def bfs(x, y):
    q.append((x, y))
    while q:
        x, y = q.popleft()
        visit[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 visit[nx][ny] == False: #1
                    visit[nx][ny] = True    
                    q.append((nx, ny))
                elif graph[nx][ny] == 0: #2
                    count[x][y] += 1
    return 1 #3

while True:
    visit = [[False]*m for _ in range(n)] #4
    count = [ [0]*m for _ in range(n) ] #5
    result = []
    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0 and visit[i][j] == False:
                result.append(bfs(i, j)) #6
    for i in range(n):
        for j in range(m):
            graph[i][j] -= count[i][j] #7
            if graph[i][j] < 0: #8
                graph[i][j] = 0
    if len(result) == 0: #9
        break
    if len(result) >= 2: #10
        check = True
        break
    year += 1 #11
if check == True: #12
    print(year)
else:
    print(0)

 

#1: 빙산이 위치하고 방문하지 않은 빙산이면, 방문처리하고 큐에 위치를 넣어준다.

#2: 빙산이 위치하지 않은 빙산 주변의 바다면 빙산주변 count +1

#3: 반복이 끝나면 빙산 1개 result 리스트에 추가

#4: 방문처리할 리스트 생성 while문 안에 넣어서 빙산 개수 셀때마다 False로 초기화

#5: 빙산 주변의 바다인 count도 while문 돌때마다 초기화

#6: 빙산 개수 result에 추가

#7: 각 빙산의 주변에 마주하고 있는 바다 면적 수 만큼 높이 빼줌

#8: 빼준 빙산의 높이가 0이거나 음수이면 높이를 0으로 고정

#9: 탐색을 끝냈는데 빙산의 개수가 0개이면 반복문 탈출(빙산이 하나도 없는 경우)

#10: 탐색을 끝냈을때 빙산의 개수가 2개 이상이면 원하는 결과니까 chek를 True로 바꾸고 반복문 탈출

#11: 반복문 마지막에 년도 1씩 추가

#12: check == True여서 원하는 결과를 얻었을때는 빙산이 2개가 될때까지 걸린 년도를 출력, 원하는 결과를 못 얻어냈으면 0을 출력

 

기존의 그래프이론 문제에서 조건을 추가한 문제입니다.

 

 

나의 bfs풀이 - 23.01.15(일)

import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]
year = 0
check = True

def bingsan(x, y): #1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0 and visit[nx][ny] == False: #2
            graph[x][y] -= 1
            if graph[x][y] < 0: #3
                graph[x][y] = 0

def bfs(x, y):
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == False and graph[nx][ny] != 0: #4
                visit[nx][ny] = True
                q.append((nx, ny))
while check: #5
    year += 1 #6
    visit = [ [False]* m for _ in range(n) ]
    cnt = 0 #7
    for i in range(n): #8
        for j in range(m):
            if graph[i][j] != 0:
                visit[i][j] = True
                bingsan(i, j)
    visit = [ [False]* m for _ in range(n) ] #9
    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0 and visit[i][j] == False: #10
                visit[i][j] = True
                bfs(i, j)
                cnt += 1
    if cnt >= 2: #11
        check = False
        break
    elif cnt == 0: #12
        break
if check == False: #13
    print(year)
else:
    print(0)

 

 

#1: 빙산을 하나씩 녹여주는 함수 - 그래서 이름도 bingsan

#2: 방향벡터로 방문한 주변 공간이 그래프의 범위 안에 들어가고, 바닷물이니까 0이고 아직 방문하지 않을때

#3: 빙산이 다 녹아버릴 경우 바닷물이 되는데 바닷물은 0으로 표현되므로, -1을 계속 진행해 0 미만으로 떨어지는것을 방지

#4: bfs는 녹은 후의 빙산의 개수를 세는 함수이다. 그래프의 범위 안에 들어가고, 방문하지 않았으며, 0이 아닐때(바닷물이 아닌 빙산일때)

#5: 언제 빙산이 2개 이상이 될지 모르기 때문에 무한반복 while문 사용

#6: 빙산이 녹는 해를 세어주는 변수 +1

#7: 빙산의 개수를 세어주는 변수

#8: 반복문을 돌며 빙산을 녹여준다

#9: 다시 사용을 해야하기 때문에 방문처리를 하는 리스트를 초기화 한다

#10: 빙산이고 방문하지 않은 장소일때

#11: 빙산이 녹은 후 개수가 2개 이상이 되었을때 check를 False로 하고, 반복문을 벗어난다.

#12: 빙산이 다 녹을 때까지 2개 이상 분리되지 않을때

#13: #11에서 걸렸다면 빙산이 2개 이상이 되는 년도를 출력, 아니라면 문제의 조건대로 0을 출력