카테고리 없음

[백준/Python] 빙산

왕초보코딩러 2024. 9. 20. 15:43
728x90

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

 


TASK

1. 1년에 얼만큼 녹는지 확인

2. 두 덩어리가 되는 지 보기 -> BFS

 


1. 하나씩 확인

 

입력

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

# 행 열
n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))
    
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

 

 

1번 태스크를 위한 함수

def count_0(nowx, nowy):
    cnt = 0
    for dx, dy in direction:
        x = nowx + dx
        y = nowy + dy
        if 0<=x<n and 0<=y<m:
            if graph[x][y] == 0:
                cnt += 1
    return cnt

상하좌우를 확인하여 0이면 cnt + 1을 한다

 

2번 태스크를 위한 함수

def bfs(graph, visited, nowx, nowy):
    queue = deque([(nowx, nowy)])
    visited[nowx][nowy] = False # 방문하면 False
    
    while queue:
        nowx, nowy = queue.popleft()
        for dx, dy in direction:
            x = nowx + dx
            y = nowy + dy
            if 0<=x<n and 0<=y<m:
                if graph[x][y] != 0 and visited[x][y] == True:
                        queue.append((x,y))
                        visited[x][y] = False

 

덩어리가 나눠지는지 확인

result = 0 # 실제 덩어리가 두 개 이상이 될 때 반환할 값
cnt = 0 # 년도 추가

# 모두 0이 아닐 때까지(모두 녹기 전까지)
while graph != [[0]*m for _ in range(n)]:
	# 얼마나 녹는지 담을 리스트
    zero = [[] for _ in range(n)]

    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0:
    	        zero[i].append(count_0(i, j))
            
    # 녹는 것만큼 뺀다
    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0:
                graph[i][j] = graph[i][j]-zero[i][j] if graph[i][j]-zero[i][j]>0 else 0
    cnt += 1 # 1년 추가
    
    visited = [[True]*m for _ in range(n)] # 방문 리스트
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0: # 바다는 False, 빙하는 True
                visited[i][j] = False
                
    res = 0 # 덩어리
    for i in range(n):
        for j in range(m):
            if visited[i][j]: # 빙하면
                bfs(graph, visited, i,j) 
                res += 1 # 덩어리 추가
                # print(i, j)
    # 두 덩어리 이상이면
    if res > 1:
        result = cnt
        break
print(result)

 

문제점: 두 번의 for문을 반복해서 돌기 때문에 python으로 실행했을 때 시간 초과

-> pypy를 사용

 

 


2. 최적화하기

for문을 없애고 최적화하기 위해

바다(0)가 아닌 빙하가 있는 위치 인덱스를 key로 한 딕셔너리를 만들고 value에 상하좌우 cnt 0을 넣었습니다.

그리고 이 딕셔너리를 for문으로 반복했씁니다.

 

입력(위와 동일)

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

# 행 열
n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))
    
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

 

1번 태스크를 위한 함수(위와 동일)

def count_0(nowx, nowy):
    cnt = 0
    for dx, dy in direction:
        x = nowx + dx
        y = nowy + dy
        if 0<=x<n and 0<=y<m:
            if graph[x][y] == 0:
                cnt += 1
    return cnt

 

2번 태스크를 위한 함수

def bfs(graph, visited, nowx, nowy):
    queue = deque([(nowx, nowy)])
    visited[nowx][nowy] = False # 방문하면 False
    
    while queue:
        nowx, nowy = queue.popleft()
        for dx, dy in direction:
            x = nowx + dx
            y = nowy + dy
            if 0<=x<n and 0<=y<m:
                if graph[x][y] != 0 and visited[x][y] == True:
                        queue.append((x,y))
                        visited[x][y] = False

 

key가 위치 인덱스이고, value가 count 0 값인 딕셔너리 nonzero

0이 아닌 빙하들 값만 저장

nonzero = {}
for i in range(n):
    for j in range(m):
        if graph[i][j] != 0:
            nonzero[(i,j)] = count_0(i,j)

 

덩어리가 나눠지는지 확인

for i in range(n) for j in range(m) 대신

for i, j in nonzero

result = 0
cnt = 0
while graph != [[0]*m for _ in range(n)]:
    # 좌표와 빙산이 - 되는 걸 같이 적는 리스트 
    for x, y in nonzero:
        graph[x][y] = max(0, graph[x][y] - nonzero[(x,y)])
    for x, y in nonzero:
        if graph[x][y] != 0:
            nonzero[(x,y)] = count_0(x,y) # 다시 업데이트
    cnt += 1
    visited = [[True]*m for _ in range(n)]
    
    res = 0
    for i, j in nonzero:
        if visited[i][j]==True and graph[i][j]!=0:
            bfs(graph, visited, i,j) 
            res += 1
                # print(i, j)
    if res > 1:
        result = cnt
        break
print(result)

 

 

결과

위: 2번 아래: 1번

물론 2번은 파이썬으로도 통과가 되었습니다

 

 

필요없는 부분은 돌지 않도록 반복문을 잘 설정해야겠다는 생각을 했습니다