[알고리즘 일기 - 파이썬] 195. 일루미네이션

문제 195. (2022-02-25)

 

5547번: 일루미네이션

Baekjoon 5547. 일루미네이션

부유한 집안의 상속자 상근이네 집은 그림과 같이 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)이다.

 

---

출력

조명을 장식하는 벽면의 길이의 합을 출력한다.

 

---

입력 예시

8 4
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 0
1 0 1 0 1 1 1 1
0 1 1 0 1 0 1 0

 

---

출력 예시

64

 

---

❧ 정답

	from sys import stdin
	from collections import deque
	w, h = map(int, stdin.readline().split())
	home = []
	for _ in range(h):
	home.append(list(map(int, stdin.readline().split())))
	cnt = 0
	# 1시 방향부터 시계방향으로
	dx = [[-1, 0, 1, 1, 0, -1], [-1, 0, 1, 1, 0, -1]] # 홀수줄, 짝수줄
	dy = [[1, 1, 1, 0, -1, 0], [0, 1, 0, -1, -1, -1]]
	def bfs(x, y):
	queue = deque([(x, y)])
	home[x][y] = 2
	cnt = 0
	while queue:
	x, y = queue.popleft()
	one = 6
	for i in range(6):
	nx = x + dx[x % 2][i]
	ny = y + dy[x % 2][i]
	if nx < 0 or ny < 0 or nx >= h or ny >= w:
	continue
	if home[nx][ny]:
	one -= 1
	if home[nx][ny] == 1:
	home[nx][ny] = 2
	queue.append((nx, ny))
	cnt += one
	return cnt
	def bfs2(x, y):
	queue = deque([(x, y)])
	home[x][y] = 3
	cnt = 0
	flag = 0
	while queue:
	x, y = queue.popleft()
	for i in range(6):
	nx = x + dx[x % 2][i]
	ny = y + dy[x % 2][i]
	if nx < 0 or ny < 0 or nx >= h or ny >= w:
	flag = 1
	continue
	if home[nx][ny] == 2:
	cnt += 1
	if home[nx][ny] == 0:
	home[nx][ny] = 3
	queue.append((nx, ny))
	if flag:
	return 0
	else:
	return cnt
	for i in range(h):
	for j in range(w):
	if home[i][j] == 1:
	cnt += bfs(i, j)
	for i in range(h):
	for j in range(w):
	if home[i][j] == 0:
	cnt -= bfs2(i, j)
	print(cnt)

view raw 0225_일루미네이션.py hosted with ❤ by GitHub