99클럽 코테 스터디 _ 10일차 TIL (BFS)

 

< 문제 >

[백준] 2573. 빙산 / 골드4

---

< 풀이 >

코드 변수 정의

• function : melt_iceberg
  • new_graph : 녹은 후의 빙산 상태 그래프 생성을 위한 리스트
  • directions : 상하좌우 탐색을 하기 위한 배열
  • sea_cnt : 빙산에 인접한 바다의 개수
• function : count_iceberg
  • iceberg_cnt : 빙산 덩어리 개수
• function : main
  • graph : 현재 빙산 상태
  • day : 경과 일수
  • max_day : 무한 루프 방지용 최대 일수

---

BFS
시간복잡도 : O(N x M)

from collections import deque

# 현재 그래프 빙산 상태에서 녹은 후의 그래프를 반환하는 함수
def melt_iceberg(graph, N, M):
    # 새로운 빙산 상태를 저장할 리스트 초기화
    new_graph = [[0] * M for _ in range(N)]
    # 상하좌우 방향 탐색
    directions = [(-1,0), (0,1), (1,0), (0,-1)]
    
    # 그래프를 순회하며 빙산의 높이를 감소
    for i in range(N):
        for j in range(M):
            if graph[i][j] != 0: # 빙산이 있는 위치
                sea_cnt = 0 # 인접한 바다 칸의 개수
                for dx, dy in directions:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 0:
                        sea_cnt += 1
                # 인접한 바다 칸의 개수만큼 높이를 감소시키지만 0 미만의 값은 가지지 않음.
                new_graph[i][j] = max(0, graph[i][j] - sea_cnt)
                
    return new_graph

# 현재 빙산 상태에서 빙산 덩어리 개수를 계산하는 함수
def count_iceberg(graph, N, M):
    # 빙산 덩어리 개수 초기화
    iceberg_cnt = 0

    visited = [[False] * (M) for _ in range(N)]
    directions = [(-1,0), (0,1), (1,0), (0,-1)]
    
    # BFS로 탐색
    def bfs(graph, i, j):
        q = deque([(i, j)])
        while q:
            x, y = q.popleft()
            visited[x][y] = True
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] != 0 and not visited[nx][ny]:
                    q.append((nx, ny))
                    visited[nx][ny] = True

    for i in range(N):
        for j in range(M):
        	# 빙산이 있고 방문하지 않았다면
            if graph[i][j] != 0 and not visited[i][j]:
                bfs(graph, i, j) # 같은 덩어리 내 빙산 방문 처리
                iceberg_cnt += 1
    
    return iceberg_cnt

# 빙산이 두 덩어리 이상으로 분리되는 데 걸리는 시간 계산하는 메인 함수
def main():
    N, M = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(N)]
    
    day = 0 # 경과 일수 초기화
    max_day = 1000 # 최대 일수 설정
    
    while max_day > 0:
        graph = melt_iceberg(graph, N, M) # 빙산 녹이기
        iceberg = count_iceberg(graph, N, M) # 현재 빙산 덩어리 수 계산
        day += 1 # 하루 경과
        max_day -= 1 # 최대 일수 감소
        
        # 빙산이 2개 이상으로 분리되었다면 경과 일수 반환
        if iceberg >= 2:
            return day
            
    # 두 덩어리 이상으로 분리되지 않는 경우
    return 0

if __name__ == "__main__":
    print(main())

---

 

 

 

풀이 방식

1. melt_iceberg 함수 : 빙산 높이를 감소시키는 함수
   • graph[i][j] 에 빙산이 존재할 경우(graph[i][j] != 0)
     • 인접한 칸 중 바다(graph[nx][ny] == 0)의 개수를 현재 빙산의 높이에서 뺀다.
   •  계산한 결과는 new_graph에 저장하여 녹은 후의 빙산 상태를 기록
     • 빙산의 높이가 음수가 되지 않도록   →    max(0, graph[i][j] - sea_cnt)
   • 갱신한 빙산 상태를 반환
2. count_iceberg 함수 : 현재 빙산 덩어리 개수를 계산하는 함수
   
   • 그래프를 순회하며 아직 방문하지 않은 빙산 칸을 찾으며 BFS를 수행
   • BFS로 한 덩어리에 연결된 모든 빙산 칸을 방문 처리한 뒤, 덩어리 개수(iceberg_cnt) + 1
   • 빙산 덩어리 개수를 반환
3. main 함수
   • 초기 빙산 상태를 입력받아 graph에 저장한다.
   • 시뮬레이션 반복
     1. melt_iceberg를 호출해 빙산 상태를 갱신
     2. count_iceberg를 호출해 현재 빙산 덩어리 개수를 계산
     3. 덩어리가 2개 이상일 경우 현재까지 경과한 시간을 반환
     4. 모든 빙산이 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 0 반환
   • 최대 반복 횟수(max_day)를 설정하여 무한 루프를 방지한다.

---

< 회고 >

🤔 💭_

문제에 나온 로직을 그대로 구현하면 쉽게 풀리는 문제인 것 같다. 다만, 위의 코드는 전체 칸을 확인하므로 빙산이 있는 칸뿐만 아니라 빙산이 없는 칸까지 불필요한 탐색이 포함된다. 좀 더 효율적으로 풀 수 있는 방법에 대한 고민을 했다.

---

빙산이 있는 칸만 탐색하는 코드

from collections import deque

def melt_iceberg(graph, N, M, ice_locations):
    melted_graph = [[0] * M for _ in range(N)] # 녹은 후 그래프
    new_locations = [] # 녹은 후에도 빙산이 있는 위치 리스트
    directions = [(-1,0), (0,1), (1,0), (0,-1)]
    
    for x, y in ice_locations:
        sea_cnt = 0
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 0:
                sea_cnt += 1
        melted_graph[x][y] = max(0, graph[x][y] - sea_cnt)
        # 녹은 후에도 빙산이 있는 경우 다시 탐색하기 위해 new_locations에 좌표 추가
        if melted_graph[x][y] > 0:
            new_locations.append((x, y))
    
    return new_locations, melted_graph

def count_iceberg_groups(graph, N, M, ice_locations):
    visited = [[False] * M for _ in range(N)]
    directions = [(-1,0), (0,1), (1,0), (0,-1)]
    groups = 0

    def bfs(start_x, start_y):
        q = deque([(start_x, start_y)])
        visited[start_x][start_y] = True
        
        while q:
            x, y = q.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if (0 <= nx < N and 0 <= ny < M and 
                    graph[nx][ny] > 0 and not visited[nx][ny]):
                    q.append((nx, ny))
                    visited[nx][ny] = True
    
    for x, y in ice_locations:
        if not visited[x][y]:
            bfs(x, y)
            groups += 1
    
    return groups

def main():
    N, M = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(N)]
    
    # 빙산이 있는 위치만 담은 리스트
    ice_locations = [(i, j) for i in range(N) for j in range(M) if graph[i][j] > 0]
    for days in range(1, 1001): # 최대 경과 일수 : 1000
        ice_locations, graph = melt_iceberg(graph, N, M, ice_locations)
        iceberg_groups = count_iceberg_groups(graph, N, M, ice_locations)
        
        # 빙산 덩어리가 2 이상 생기는 경우
        if iceberg_groups >= 2:
            return days
    
    return 0

if __name__ == "__main__":
    print(main())