문제 정보
문제 정리
봄의 기운, 여름의 기운, 가을의 기운이라는 이름의 게이지 3개가 있으며, 세 게이지의 합은 항상 3N이다. 궁기의 공격에 피격당하면 봄의 기운이 +a, 가을의 기운이 -a만큼 변한다. 도올의 공격에 피격당하면 여름의 기운이 +b, 봄의 기운이 -b만큼 변한다. 혼돈의 공격에 피격당하면 가을의 기운이 +c, 여름의 기운이 -c만큼 변한다. 계절의 균형을 이루려면 어떤 게이지도 (0, 2N) 범위 내에 있어야 한다. 위와 같은 조건을 만족하면서 시작 게이지에서 공격에 적절하게 피격당해 세 게이지를 전부 N의 값으로 만들기 위한 최소 피격횟수를 구하고, 그때의 피격 순서도 구해야 한다.
풀이
우선 세 게이지의 총합이 3N으로 일정하므로, 봄의 기운의 값, 여름의 기운의 값이 정해질 경우 자동적으로 (가을의 기운) = 3N - (봄의 기운) - (여름의 기운) 이 된다. 따라서 봄의 기운을 x, 여름의 기운을 y로 두고 BFS 탐색으로 visited[N][N]에 도달 가능한지 체크하면 된다.
역추적은 따로 배열을 생성할 필요 없이 visited에 궁기에 피격당했으면 0, 도올에 피격당했으면 1, 혼돈에 피격당했으면 2를 저장한다. 이 경우 끝점에서 피격당한 공격에 의해 조절된 게이지를 복구해가며 이동하다보면 출발점으로 돌아올 수 있다.
또한 사전순으로 가장 앞서는 피격 순서 문자열을 출력해야 하는데, 그냥 BFS에서 피격 순서를 정할 때 현재 게이지에서 (궁기에게 피격될 경우) -> (도올에게 피격될 경우) -> (혼돈에게 피격될 경우) 순서로 처리해주면 자연스럽게 사전 순으로 가장 앞서는 문자열이 도출된다.
카링은 귀엽다!
코드
# 백준 34006
import io
from collections import deque
input = io.BufferedReader(io.FileIO(0), 1<<18).readline
def BFS(N, start, delta, visited):
dx = (delta[0], -delta[1], 0)
dy = (0, delta[1], -delta[2])
maxG = 2*N
tMaxG = 3*N
q = deque()
q.append((start[1], start[0]))
visited[start[1]][start[0]] = 4
while q:
curY, curX = q.popleft()
if curY == N and curX == N:
return
for i in range(3):
nextX = curX + dx[i]
nextY = curY + dy[i]
if 0 <= nextX < maxG and 0 <= nextY < maxG and N < nextX+nextY < tMaxG and visited[nextY][nextX] == -1:
visited[nextY][nextX] = i
q.append((nextY, nextX))
def solve(N, start, delta):
# BFS 탐색
visited = [[-1] * (2*N) for _ in range(2*N)]
BFS(N, start, delta, visited)
# 게이지를 안정화하지 못한 경우
if visited[N][N] == -1:
return [-1]
# 피격 순서 역추적
traceback = []
curX = N
curY = N
while True:
curV = visited[curY][curX]
if curV == 4:
break
elif curV == 0:
traceback.append('A')
curX -= delta[0]
elif curV == 1:
traceback.append('B')
curX += delta[1]
curY -= delta[1]
elif curV == 2:
traceback.append('C')
curY += delta[2]
return [len(traceback), ''.join(traceback[::-1])]
def main():
N = int(input())
start = tuple(map(int, input().split()))
delta = tuple(map(int, input().split()))
for i in solve(N, start, delta):
print(i)
main()
