[백준] 2573 빙산

문제

---

풀이 과정

1) 문제 이해 및 접근

빙산이 하나의 덩어리로 뭉쳐있는지 확인이 필요하여 DFS 탐색을 이용하여 확인

또한, 시간이 흐름에 따라 빙산이 녹아야 하므로 2차원 배열을 돌면서 값을 줄이려고 함

2차원 배열을 계속해서 반복하면 시간초과가 우려되어, 주변에 0의 개수를 기억하게 하여 시간을 줄이려고 시도

그리하여 초기에 시간의 흐름에 따라 2차원 배열을 모두 반복해서 빙산이 녹게 만들어주고, 다시 DFS 탐색으로 덩어리 분리 여부를 확인하는 방식으로 접근

 

그러나 배열의 크기가 최악의 경우 300 * 300 으로 반복적인 2차원 배열의 반복 확인으로 시간초과가 발생

빙산이 녹는 과정을 DFS 탐색을 하면서 주변에 바다의 개수를 확인하여 빙산이 녹는 과정과 덩어리를 확인하는 과정을 하나로 합쳐서 2차원 배열을 여러번 반복하는 로직을 삭제

2) 알고리즘

• 델타 탐색
• DFS

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')


def DFS(y, x, num):                                     # 좌표, 빙산 덩어리 번호
    stack = [(y, x)]                                    # 스택에 시작 좌표 추가

    while stack:                                        # 이어진 빙산이 있으면
        node = stack.pop()                              
        if not visited[node[0]][node[1]]:               # 현재 좌표가 아직 방문하지 않은 빙산인 경우
            visited[node[0]][node[1]] = num             # 빙산에 번호를 매김 (방문 처리)
            minus = 0                                   # 현재 위치 주변에 바다의 개수 카운트 위한 변수 
            for k in range(4):                          # 동서남북 탐색
                r = node[0] + dr[k]
                c = node[1] + dc[k]
                
                if not visited[r][c]:                   # 주변 좌표가 아직 방문하지 않았으면
                    if board[r][c] <= 0:                # 바다라면 바다 개수 증가
                        minus += 1
                    elif board[r][c]:                   # 빙산이면, 다음 탐색을 위해 스택에 추가
                        stack.append((r, c))

            board[node[0]][node[1]] -= minus            # 현재 빙산이 주변 바다 개수만큼 녹음
            if board[node[0]][node[1]] <= 0:            # 녹아서 바다가 됬으면, 빙산 좌표가 있는 딕셔너리 변수에서 녹은걸로 표시
                coordinates[(node[0], node[1])] = 0


dr = [-1, 0, 1, 0]                  # 델타 탐색
dc = [0, 1, 0, -1]

N, M = map(int, sys.stdin.readline().split())                                   # 행의 개수, 열의 개수
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]        # 빙산의 정보들
coordinates = {}                                                                # 좌표값들 저장하는 딕셔너리 변수 (Key-좌표 값, Value-빙산 존재 유무)
year = 0                                                                        # 년도

for i in range(1, N-1):                         # 초기에 2차원 배열을 한번 탐색하여 빙산이 존재하는 좌표 값 구함
    for j in range(1, M-1):                     # 추후 빙산이 있는 좌표 반복문의 횟수를 줄이기 위함
        if board[i][j]:
            coordinates[(i, j)] = 1


while sum(coordinates.values()) > 0:            # 빙산이 하나라도 존재하면 반복
    visited = [[0] * M for _ in range(N)]       # 빙산이 녹은걸 계산했는지 좌표 값 (좌표 방문 여부)
    num = 1                                     # 빙산 덩어리 번호

    for k, v in coordinates.items():            # 빙산이 있는 좌표 값만 반복
        if v and not visited[k[0]][k[1]]:       # 빙산이 있고, 아직 확인하지 않은 빙산일때
            if num == 2:                        # 만약에 빙산 덩어리가 2번 이면, 빙산이 두개 이상으로 분리 되었으므로 종료
                print(year)
                break
            DFS(k[0], k[1], num)                # DFS 탐색
            num += 1                            # 빙산 덩어리 하나 찾았으니, 빙산 번호 증가

    else:                                       # 빙산 덩어리가 하나이면
        year += 1                               # 시간 증가 및 다음 진행
        continue
    break                                       # 빙산 덩어리가 두개 이상으로 종료 되었으면, 전체 반복문도 종료

else:                                           # 빙산이 두개 이상으로 나누어지지 않으면 0 반환
    print(0)

---

결과 및 학습한 내용

1) 어려웠던 내용

빙산이 녹는게 주변에 바다의 인접한 개수만큼 줄어들게 되는데, 단순히 2차원 배열을 반복하게 되면 값에 차이가 발생하게 되는데, 이런 오류를 피하기 위해 고민을 많이 함

시간 단축을 하기 위해서 2중 반복문을 최대한 줄이는것에 어려움을 겪음

2) 새롭게 학습한 내용

탐색과 값을 변경하는것을 분리하면 시간 초과가 발생할 확률이 높다

우선적으로 작동하는 로직을 구현하고, 두개의 기능을 합쳐도 무리가 생기지 않는다면 합치는게 효율성 측면에서 더 뛰어날 수 있다

---

문제 링크

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

2573번: 빙산

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다