5547번: 일루미네이션
첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는
www.acmicpc.net
문제
부유한 집안의 상속자 상근이네 집은 그림과 같이 1미터의 정육각형이 붙어있는 상태이다. 크리스마스가 다가오기 때문에, 여자친구에게 잘 보이기 위해 상근이는 건물의 벽면을 조명으로 장식하려고 한다. 외부에 보이지 않는 부분에 조명을 장식하는 것은 낭비라고 생각했기 때문에, 밖에서 보이는 부분만 장식하려고 한다.
위의 그림은 상공에서 본 상근이네 집의 건물 배치이다. 정육각형 안의 숫자는 좌표를 나타낸다. 여기서 회색 정육각형은 건물의 위치이고, 흰색은 건물이 없는 곳이다. 위에서 붉은 색 선으로 표시된 부분이 밖에서 보이는 벽이고, 이 벽에 조명을 장식할 것이다. 벽의 총 길이는 64미터이다.
상근이네 집의 건물 위치 지도가 주어졌을 때, 조명을 장식할 벽면의 길이의 합을 구하는 프로그램을 작성하시오. 지도의 바깥은 자유롭게 왕래 할 수 있는 곳이고, 인접한 건물 사이는 통과할 수 없다.
입력
첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 (j, i)이며, 건물이 있을 때는 1이고, 없을 때는 0이다. 주어지는 입력에는 건물이 적어도 하나 있다.
지도는 다음과 같은 규칙에 의해 만들어졌다.
- 지도의 가장 왼쪽 위에 있는 정육각형의 좌표는 (1,1)이다.
- (x,y)의 오른족에 있는 정육각형의 좌표는 (x+1,y)이다.
- y가 홀수 일 때, 아래쪽에 있는 정육각형의 좌표는 (x,y+1)이다.
- y가 짝수 일 때, 오른쪽 아래에 있는 정육각형의 좌표는 (x,y+1)이다.
출력
조명을 장식하는 벽면의 길이의 합을 출력한다.
코드
from collections import deque
w, h = map(int, input().split())
map_data = []
map_data.append([0] * (w+2))
for i in range(h):
map_data.append([0] + list(map(int, input().split())) + [0])
map_data.append([0] * (w+2))
q = deque([(0, 0)])
visited = [[False] * (w+2) for _ in range(h+2)]
visited[0][0] = True
cnt = 0
while q:
now_r, now_c = q.popleft()
if now_r % 2 == 1:
dir = [(-1, 1), (0, 1), (1, 1), (1, 0), (0, -1), (-1, 0)]
else:
dir = [(-1, 0), (0, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
for i in range(6):
nr = now_r + dir[i][0]
nc = now_c + dir[i][1]
if 0 <= nr < h+2 and 0 <= nc < w+2:
if map_data[nr][nc] == 0 and not visited[nr][nc]:
q.append((nr, nc))
visited[nr][nc] = True
elif map_data[nr][nc] == 1:
cnt += 1
print(cnt)
우선 계산을 쉽게 하기 위해 입력으로 받은 데이터에 외곽 땅을 추가해준다.패딩을 추가해주는 것이다. 예를 들어 아래 예시처럼 입력이 들어오면
map_data 2차원 배열에는 다음과 같이 저장된다. 바깥 테두리에 빈 땅을 추가해준다고 생각하면 된다.
이제 (0, 0)에서부터 BFS를 돌며 외곽 땅에서 건물이 있는 땅으로 가는 경우만 세주면 된다. 이때 주의해야할 점은 땅이 육각형 모양이라 현재 보고 있는 칸의 행이 홀수일 때와 짝수일 때를 구분하여 다음에 탐색할 칸을 정해주어야 한다.
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 16508번 전공책 (0) | 2023.06.24 |
---|---|
[Python/파이썬] 백준 2636번 치즈 (0) | 2023.06.23 |
[Python/파이썬] 백준 14940번 쉬운 최단거리 (0) | 2023.06.21 |
[Python/파이썬] 백준 1600번 말이 되고픈 원숭이 (0) | 2023.06.19 |
[Python/파이썬] 백준 13023번 ABCDE (0) | 2023.04.25 |