[백준] 14714번: 홍삼게임 (Easy) - Python

https://www.acmicpc.net/problem/14714

14714번: 홍삼 게임 (Easy)

문제 유형을 보면 힌트를 얻을 수 있는데, BFS를 사용하여 풀 수 있는 문제였다.. 

 방문 처리를 할 때 지목권 a를 가질 사람을 탐색 & 지목권 b를 가질 사람을 탐색 해야 하며 각 turn 마다 지목은 한번만 하므로 이를 3차원 배열로 나타낼 수 있다는 것이 이 문제의 핵심이었다 

즉 이를 3차원 배열로 표현하게 되면 

visited[지목권 종류][a 지목][b 지목]

가 된다. 

BFS 탐색 코드에서는 queue 에서 꺼내어 확인하는데, 현재의 turn 이 홀수면 A를 지목하게 되고 짝수면 B를 지목하게 된다. 

if count % 2 == 1: # A
	...
else: # B
	...

방문처리를 할 때 이미 다른 지목권을 가지고 있는 경우라면 게임이 끝나는 것이므로 queue에 담지 않으면 된다. 

if visited[0][left_a][cur_b] == 0:
    visited[0][left_a][cur_b] = count + 1
    queue.append((left_a, cur_b, count+1))
if visited[0][right_a][cur_b] == 0:
    visited[0][right_a][cur_b] = count + 1
    queue.append((right_a, cur_b, count+1))

 

전체 코드 

 

# https://www.acmicpc.net/problem/14714
from collections import deque

n, a, b, da, db = map(int, input().split())
a -= 1
b -= 1 # index 맞추기

#  visited[a or b][a누구][b누구]

visited = [[[0] * n for _ in range(n)] for _ in range(2)] # 3차원 배열
visited[0][a][b] = 1 # 0 == a 지목권
visited[1][a][b] = 1 # 1 == b 지목권
queue = deque([(a, b, 1)]) # 현재 지목권 가진 사람 a, b, 지목 횟수

while queue:
    cur_a, cur_b, count = queue.popleft()
    if count % 2 == 1: # A
        left_a = cur_a - da
        right_a = cur_a + da
        if left_a < 0:
            left_a += n
        if right_a >= n:
            right_a -= n
        # 방문 처리
        if visited[0][left_a][cur_b] == 0:
            visited[0][left_a][cur_b] = count + 1
            queue.append((left_a, cur_b, count+1))
        if visited[0][right_a][cur_b] == 0:
            visited[0][right_a][cur_b] = count + 1
            queue.append((right_a, cur_b, count+1))
    else: # B
        left_b = cur_b - db
        right_b = cur_b + db
        if left_b < 0:
            left_b += n
        if right_b >= n:
            right_b -= n

        if visited[1][cur_a][left_b] == 0:
            visited[1][cur_a][left_b] = count + 1
            queue.append((cur_a, left_b, count+1))
        if visited[1][cur_a][right_b] == 0:
            visited[1][cur_a][right_b] = count + 1
            queue.append((cur_a, right_b, count+1))

INF = int(1e9)
answer = INF
# min 값 찾기
for i in range(n):
    if visited[0][i][i] != 0 and visited[0][i][i] < answer:
        answer = visited[0][i][i]
    if visited[1][i][i] != 0 and visited[1][i][i] < answer:
        answer = visited[1][i][i]

if answer == INF:
    print("Evil Galazy")
else:
    print(answer-1)