문제 링크

문제 해설

Idea

  • 전체 좌표 평면의 외곽에 1만큼의 여백을 추가하고 x,y 좌표가 0부터 시작한다고 판단
  • y가 홀수 일 때, 인접한 좌표는 상하좌우와 함께 우상단,우하단을 포함
  • y가 짝수 일 때, 인접한 좌표는 상하좌우와 함께 좌상단, 좌하단을 포함
  • 건물이 없는 좌표를 BFS 탐색하면서 건물과 만나는 지점을 카운트

Time Complexity

  • BFS: O(N^2) = 10,000

Data Size

  • W, H: 1 <= int <= 100

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

from collections import deque
import sys
input = sys.stdin.readline

W, H = map(lambda x: int(x)+2, input().split())
maps = [[0] * W for _ in range(H)]
for i in range(1,H-1):
    maps[i] = [0]+list(map(int, input().split()))+[0]
visited = [[False] * W for _ in range(H)]

def bfs(start):
    queue = deque([start])
    dy = [0,1,0,-1,1,-1]
    cnt = 0

    while queue:
        y,x = queue.popleft()
        dx = [-1,0,1,0,-1,-1] if y%2==0 else [-1,0,1,0,1,1]
        for i in range(6):
            ny, nx = y+dy[i], x+dx[i]
            if 0<=ny<H and 0<=nx<W:
                if maps[ny][nx] == 0 and not visited[ny][nx]:
                    queue.append((ny,nx))
                    visited[ny][nx] = True
                elif maps[ny][nx] == 1:
                    cnt += 1
    return cnt

visited[0][0] = True
print(bfs((0,0)))