[PYTHON] 백준 2573 - 빙산

성능 요약

메모리: 218500 KB, 시간: 748 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 구현

문제 설명

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

	2	4	5	3
	3		2	5	2
	7	6	2	4

그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

		2	4	1
	1		1	5
	5	4	1	2

그림 2

			3
				4
	3	2

그림 3

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

---

아이디어, 문제풀이

• 빙산은 음수가 되면 0이다.
• 이전에 풀이했던 백준 11724번과 같이 총 대륙이 몇개인지를 찾아내면 되는 문제.
  https://www.acmicpc.net/problem/11724
  알고리즘 자체는 어렵지 않다.
• 매년 대륙의 상태를 알기 위해 대륙이 녹은후를 보여주는 알고리즘도 필요하다.

---

TROUBLE SHOOTING

• 함수형 두개로 문제를 풀이한건 거의 최초다. 최대한 한 함수 안에서 구현을 해보고 싶었는데, 진행 할수록 변수들도 겹치게 되고, 녹은땅을 만든 다음 그 땅들이 일치하는지를 한번에 생각하려다 보니 머리가 안굴러가는게 느껴졌다. 아래는 내가 구현하다 실패했던 코드다. 말 그대로 한개로 다 해보려다가… 실패…

  for i in range(n):
          for j in range(m):
              if land[i][j] == 1:
                  visit_stack.append((x,y))
  
      while visit_stack:
  
          for i in range(4):
  
              a, b = visit_stack.pop()
  
              na = a + da[i] # 0일때 아래로, 1일때 위로
              nb = b + db[i] # 2일때 오르쪽, 3일때 왼쪽
  
              if 0 <= x < n and 0 <= y < m:
                  if land[na][nb] == 1:
                      visit[na][nb] = 1
                      visit_stack.append((na,nb))
              else:
                  continue

• 이코드에서 내가 만든 함수는 총 2개로, 아래와 같다.

  1. def continent(graph, land, n, m):

     한번 호출할 때마다 1년후의 대륙상태를 1, 0으로 표현함. land에 저장후 리턴.

  2. def dfs(land, n, m, visit):

     land를 가져와 총 대륙이 몇개인지를 확인함.

     처음부터 이런 식으로 알고리즘을 짜고 구현했다면 많은시간이 걸리진 않았을텐데… 아쉬운 부분이 많다.

• 경험이 쌓이며 코드 자체는 구현하는데에 어렵지 않았는데, 아래 처럼 입력값을 체크해보고 있을때 자꾸 올바른 값을 뽑아내지 못했다.

  land= [[0] * m for _ in range(n)]
  visit= [[0] * m for _ in range(n)]
  conti = continent(graph, land, n, m)
  answer = dfs(conti, n, m, visit)
  print(conti)
  print(answer)

  나는 당연히 dfs알고리즘이 잘못됐다고 생각하며 수정을 하고 있었는데, 출력부분을 살펴보니, 문제가 있었다. continent 함수에서도 visit을 사용하고, answer에서도 visit을 사용하니, 중간에 한번더 초기화를 해주거나 새로운 배열로 초기화를 해줘야 했던 것이다!!!!!!!!!!!!! 코드가 길어지니… 실수를 찾아내는것도 쉽지가 않았다… 꼼꼼함이 생명이다. 정말 저쪽에는 문제가 없을거라 생각했는데, 그냥 코드를 읽어보기만해도 문제가 된다는걸 알 수 있을정도로 간단한 실수였다 ;ㅁ; 초기화방법을 바꿔주니 제대로된 답이 나왔다… 더슬퍼 ;ㅁ;
  
• 위 코드를 수정해서 문제가 원하는 출력값을 만들어 줘야 했는데, 머리로는 쉽게 짠 코드를 직접 쓰려고 보니, “그래서 전부다 녹은건 어떻게 표현해야하는거지?” 랑, “분열된건 어떻게 확인하지?” 같은 생각들이 머리를 스쳤다. 많은 시간들을 잡아먹고, 결국 chat gpt와 자료들을 참고해 코드를 구현했다.

  year = 0
  while True:
      # 빙산 녹는 과정
      land = [[0] * m for _ in range(n)]
      conti = continent(graph, land, n, m)
  
      # 대륙 개수 계산
      visit = [[0] * m for _ in range(n)]
      answer = dfs(conti, n, m, visit)
  
      # 대륙이 분열되었는지 확인
      if answer > 1:
          print(year)
          break
  
      # 빙산이 모두 녹았는지 확인
      if sum(sum(row) for row in graph) == 0:
          print(0)
          break
  
      year += 1

  해매면 해맬수록 더 완벽하게 공부가 되는 느낌이 들긴 하는데… 쓰는 시간이 너무 많다. 양날의 검 같은 느낌… 그래도 문제는 완벽하게 이해하고 마무리 한것 같다.
  

---

코드

#https://www.acmicpc.net/problem/2573
#빙산
#2573

import sys
input = sys.stdin.readline

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

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

# print(graph)

visit= [[0] * m for _ in range(n)]
land= [[0] * m for _ in range(n)]

# print(visit)

dx = [1, -1, 0, 0] #위아래
dy = [0, 0, 1, -1] #오른쪽왼쪽

#년수를 카운트 해야함

def continent(graph, land, n, m): #year

    stack = []
    # stack.append((a, b))
    visit_stack = []

    #1년이 지날때마다 0이 아닌곳을 주변의 상황에 따라 -1,-2,-3 해줘야함
    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0:
                stack.append((i,j))
                land[i][j] = 1
                
    while stack:
        
        x, y = stack.pop()
        # land[x][y] = 1

        visit[x][y] = 1

        for i in range(4):

            nx = x + dx[i] # 0일때 아래로, 1일때 위로
            ny = y + dy[i] # 2일때 오른쪽, 3일때 왼쪽
        

            if land[nx][ny] == 0:
                graph[x][y] -= 1
                if graph[x][y] < 0:
                    graph[x][y] = 0
            else:
                continue

    # print(stack)
    # print(graph)
    # print(land)
    return land

da = [1, -1, 0, 0] #위아래
db = [0, 0, 1, -1] #오른쪽왼쪽

def dfs(land, n, m, visit):

    visit_stack = []
    value = 0

    for x in range(n):
        for y in range(m):
            if land[x][y] == 1 and visit[x][y] == 0:
                value += 1  # 대륙을 발견할 때마다 value를 증가시킵니다.
                visit_stack.append((x, y))
                visit[x][y] = 1

                while visit_stack:
                    a, b = visit_stack.pop()

                    for i in range(4):
                        na = a + da[i]
                        nb = b + db[i]

                        if 0 <= na < n and 0 <= nb < m and land[na][nb] == 1 and visit[na][nb] == 0:
                            visit[na][nb] = 1
                            visit_stack.append((na, nb))

    return value

year = 0
while True:
    # 빙산 녹는 과정
    land = [[0] * m for _ in range(n)]
    conti = continent(graph, land, n, m)

    # 대륙 개수 계산
    visit = [[0] * m for _ in range(n)]
    answer = dfs(conti, n, m, visit)

    # 대륙이 분열되었는지 확인
    if answer > 1:
        print(year)
        break

    # 빙산이 모두 녹았는지 확인
    if sum(sum(row) for row in graph) == 0:
        print(0)
        break

    year += 1