[백준] 해변(python)

백준, 해변

14397번: 해변

TL;DR

• 그래프 탐색

문제 요약

1. 정육각형으로 이루어져 있는 지도가 주어졌을 때, 해변의 길이를 구하는 프로그램을 작성하라.
2. 해변은 물(.)과 땅(#)이 맞닿아 있는 곳을 의미힌다.

 

- 섬의 개수 구하기와 같은 문제에서는 노드가 정사각형으로 되어 있어 노드를 방문하며 해당 노드의 4방위를 탐색하는 식으로 문제를 해결할 수 있었다. 하지만 이 문제의 경우 정육각형 형태로 주어졌다는 것이 기존의 문제와 차이점이다.

- 지도를 직접 그렸을 때, 규칙성을 찾아내서 그래프를 탐색하는 것을 통해 문제를 해결할 수 있다.

입출력 형태

입출력 예시

 

주어진 입출력예시 자체로는 문제를 이해하기 어려울 수 있기 때문에 직접 그려보면 도움이 된다.

그림으로 그린 입출력 예시

 

예시 1과 2에 대해서 그림으로 표현하면 해변의 의미를 확실히 확인할 수 있다.

풀이

예시 2번을 표현한 그림에서 해변의 길이를 구하기 위한 규칙을 찾을 수 있다.

1. 같은 행(가로줄)에 대해서 방문한 노드가 물 노드이고 그 다음 노드가 땅 노드라면 해변의 길이를 추가한다.
2. 육각형이기 때문에 단순 방문 노드의 상-하가 아닌 모양에서 규칙을 찾아야 한다.
   1. 방문한 행이 짝수일 경우(0번 포함), 방문한 노드의 바로 아래와 좌측 대각선 아래 노드를 확인하여 해변의 길이를 증가시키야 한다.
   2. 방문한 행이 홀수일 경우, 방문한 노드의 바로 아래와 우측 대각선 아래, 좌측 대각선 아래 노드를 확인하여 해변의 길이를 증가시켜야 한다.

이러한 규칙을 코드로 구현하면 답을 얻을 수 있다.

import sys
INPUT = sys.stdin.readline

N, M = map(int, INPUT().split())
stack = []
for _ in range(N):
    info = INPUT()[:-1]
    line = []
    for c in info:
        line.append(c)
    stack.append(line)

count = 0
for y in range(N):
  for x in range(M-1):
    if (stack[y][x] == "." and stack[y][x+1] == "#") or (stack[y][x] == "#" and stack[y][x+1] == "."):
      count += 1

for y in range(N-1):
  if y%2 == 0:
    if (stack[y][0] == "." and stack[y+1][0] == "#") or (stack[y][0] == "#" and stack[y+1][0] == "."):
      count += 1
    for x in range(1,M):
      if (stack[y][x] == "." and stack[y+1][x] == '#') or (stack[y][x] == "#" and stack[y+1][x] == '.'):
        count += 1
      if (stack[y][x] == "." and stack[y+1][x-1] == '#') or (stack[y][x] == "#" and stack[y+1][x-1] == '.'):
        count += 1
  else:
    for x in range(M-1):
      if (stack[y][x] == "." and stack[y+1][x] == '#') or (stack[y][x] == "#" and stack[y+1][x] == '.'):
        count += 1
      if (stack[y][x] == "." and stack[y+1][x+1] == '#') or (stack[y][x] == "#" and stack[y+1][x+1] == '.'):
        count += 1
    if (stack[y][M-1] == "." and stack[y+1][M-1] =="#") or (stack[y][M-1] == "#" and stack[y+1][M-1] =="."):
      count += 1

print(count)

 

명시한 조건 별로 나누어 코드로 구현하였다. 그래프 탐색 문제이기 때문에 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)로 문제를 해결할 수 있을 것이라고 생각했지만 해당 방법으로는 문제를 풀 지 못하였다. 추후 문제를 풀게 된다면 포스트에 업데이트할 수 있도록 하겠다.