[백준/1109] 섬 (Python)

Problem : https://www.acmicpc.net/problem/1109

1109번: 섬

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 01:13:40

 

---

 

문제 설명

 

지민이는 보물을 찾아 떠나기 위해 섬과 바다가 그려져 있는 지도를 샀다. 지도는 N×M 크기의 직사각형 모양이고, 각각의 1×1크기의 칸에는 ‘x’ 또는 ‘.’중의 하나가 쓰여 있다.

바다는 ‘.’이 가로로 또는 세로로 최대로 연결되어 있는 그룹이다. 섬은 ‘x’가 가로, 세로, 또는 대각선으로 최대로 연결되어 있는 그룹이다.

만약 어떤 섬이 다른 섬을 포함하고 있지 않는다면, 그 섬은 높이가 0이다. 만약 어떤 섬A가 포함하고 있는 섬중에 가장 높이가 높은 섬의 높이가 K라면, 그 섬 A의 높이는 K+1이다.

섬 A가 섬 B를 포함한다는 말은, 일단 A와 B가 다르고, 섬 B의 어느 곳에서 출발해도 A의 밖으로 나갈 수 없을 때이다. 이때 대각선으로 이동은 불가능하다.

다음과 같은 지도를 보자.

 

xxx.x...xxxxx        000.0...11111
xxxx....x...x        0000....1...1
........x.x.x        ........1.4.1
..xxxxx.x...x        ..55555.1...1
..x...x.xxx.x        ..5...5.111.1
..x.x.x...x..        ..5.3.5...1..
..x...x...xxx        ..5...5...111
...xxxxxx....        ...555555....
x............        2............

 

섬은 총 6개가 있다. 높이가 0인 섬은 5개이다. (0~4) 그리고, 높이가 1인 섬은 1개 있다. (5) 3번 섬에서 출발해서 5번 섬의 밖으로 나갈 수 없기 때문에 섬5는 섬3을 포함하고 있는 것이다. 하지만, 섬4에서 출발해서 섬1을 나갈 수 있으므로, 섬1은 섬4를 포함하고 있는 것이 아니다.

지도가 주어졌을 때, 높이가 0인 섬의 개수부터 높이가 M인 섬의 개수까지를 차례대로 출력하는 프로그램을 작성하시오. M은 지도에 있는 섬 중에서 가장 높은 높이이다.

 

입력 및 출력

 

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 섬의 지도가 주어진다.

 

출력

첫째 줄에 높이가 0인 섬의 개수, 높이가 1인 섬의 개수, …, 높이가 M인 섬의 개수 까지 공백으로 구분해서 출력한다. 만약 섬이 하나도 없을 때는 -1을 출력한다.

 

입력 예시

10 5
xxxxx
x...x
x.x.x
x...x
xxxxx
xxxxx
x...x
x.x.x
x...x
xxxxx

 

출력 예시

2 1

 

 

---

 

풀이

BFS / DFS로 어디까지 할 수 있니? 를 물어보는 문제. 나같은 경우는 총 2회의 DFS 알고리즘, 1회의 BFS 알고리즘을 사용했다.

 

• DFS 1 : 모든 map을 순회하며, 섬을 발견할 때마다 섬에 속하는 모든 원소를 방문 후 섬을 카운팅한다. 여기서는 가로, 세로, 대각선을 이동한다.
• DFS 2 : 사실상의 핵심. DFS 1을 구하며 우리는 섬을 발견했다. 즉  각 섬의 시작 좌표에서 다음 두 가지를 조사한다.
  • map 바깥 쪽으로 나갈 수 있는지 여부
  • 바다를 통해서 다른 섬에 방문할 수 있는지 여부(인접 섬)
• BFS : DFS 2에서 map 바깥 쪽으로 나갈 수 있는 섬들을 root로 삼아, 모든 섬들의 height를 구한다. 포함하는 섬이 없다면 height는 0이 되고, 포함하는 섬이 있다면 그 섬들의 height 중 max값 + 1이 height가 된다.

이를 통해서 최종적으로 score list(height list)가 완성되고, 이를 height = 0부터 최댓값까지 출력하면 된다.

 

...최근 시간단축을 목표로 삼고 코딩테스트를 준비하고 있는데, 1시간이 넘는 시간이 소모되니 약간 식겁했다...

 

 

풀이 코드

from collections import Counter
import sys

input = sys.stdin.readline
dx = [-1, 1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, -1, 1, 1, -1, 1, -1]


def init() :
  global N, M, map_list
  N, M = map(int, input().split())
  map_list = [input().strip() for _ in range(N)]

def full_dfs(x, y, idx, visited) :
  q = [(x, y)]
  visited[y][x] = idx
  
  while q :
    x, y = q.pop()

    for k in range(8) :
      ax, ay = x + dx[k], y + dy[k]
      if -1 < ax < M and -1 < ay < N and map_list[ay][ax] == 'x' and visited[ay][ax] == -1 :
        visited[ay][ax] = idx
        q.append((ax, ay))

def inside_dfs(x, y, idx, visited) :
  is_outside = False
  contact_set = set()
  q = [(x, y)]

  while q :
    x, y = q.pop()

    for k in range(4) :
      ax, ay = x + dx[k], y + dy[k]
      if -1 < ax < M and -1 < ay < N :
        if visited[ay][ax] == -1 :
          visited[ay][ax] = idx
          q.append((ax, ay))
        elif visited[ay][ax] != idx :
          contact_set.add(visited[ay][ax])
      else :
        is_outside = True

  return is_outside, contact_set

def full_search() :
  global visited, target_node
  visited = [[-1]*M for _ in range(N)]
  target_node = list()
  idx = 0
  
  for i in range(N) :
    for j in range(M) :
      if map_list[i][j] == 'x' and visited[i][j] == -1 :
        full_dfs(j, i, idx, visited)
        target_node.append((j, i))
        idx += 1

def bfs(node, contact_dict, score_list, visited) :
  nxt_list = list()
  for nxt in contact_dict[node] :
    if not visited[nxt] :
      visited[nxt] = True
      nxt_list.append(nxt)

  result = 0
  for nxt in nxt_list :
    result = max(result, bfs(nxt, contact_dict, score_list, visited) + 1 )

  score_list[node] = result
  return result
  
  

def inside_search() :
  score_list = list()
  outside_list = list()
  contact_dict = dict()
  for idx, (x, y) in enumerate(target_node) :
    local_visited = [_visited[:] for _visited in visited]
    is_outside, contact_set = inside_dfs(x, y, idx, local_visited)
    
    if is_outside :
      outside_list.append(idx)
      
    contact_dict[idx] = contact_set

  for i in range(idx+1) :
    for j in contact_dict[i] :
      contact_dict[j].add(i)

  
  inside_visited = [ x in outside_list for x in range(idx+1)]
  score_list = [0]*(idx+1)

  
  for node in outside_list :
    bfs(node, contact_dict, score_list, inside_visited)
    
  maxval = max(score_list)
  counter = Counter(score_list)
  fscore_list = [0]*(maxval+1)
  for key, val in counter.items() :
    fscore_list[key] = val

  print(*fscore_list)

def solve() :
  init()
  full_search()
  if not target_node :
    print(-1)
    return
  inside_search()

solve()

풀이 완료!