원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
게임
원제: 게임
문제
앨리스와 밥은 개의 방과 이 방들을 연결하는 통로들로 이루어진 미로에서 게임을 하려고 한다.
미로의 방에는 의 번호가 붙어 있다. 미로의 어떤 방들은 출구를 가지고 있는데, 번 방에는 이면 출구가 있고, 이면 없다.
미로를 연결하는 통로는 정확히 쌍의 방 중 하나의 쌍을 연결한다. 같은 쌍의 방을 잇는 통로가 여러 개 존재할 수 있다.
구체적으로는, 각 에 대하여, 번 방과 번 방을 잇는 서로 다른 통로가 개 존재한다.
임의의 두 방 사이를 통로들을 통해 오갈 수 있음이 보장되지 않음에 유의하라.
앨리스와 밥은 총 번의 게임을 하려고 하는데, 번째 게임은 다음과 같이 진행된다.
- 앨리스가 미로의 번 방으로 들어간다.
- 앨리스는 다음 규칙에 따라 인접한 방으로 이동할 수 있다.
- 앨리스가 현재 번 방에 있다 하자. 앨리스는 번 방과 연결된 개의 서로 다른 통로를 고른다. 이때 같은 방을 연결하는 여러 통로를 동시에 고를 수 있다. 만약 번 방과 연결된 통로의 수가 보다 작아 서로 다른 개의 통로를 고르는 것이 불가능할 경우, 이동할 수 없다.
- 앨리스가 선택을 마친 후 밥은 앨리스가 고른 개의 통로 중 하나를 고른다.
- 앨리스는 밥이 고른 통로가 잇는 반대쪽 방으로 이동한다.
- 앨리스가 위 규칙에 따라 다른 방으로 이동하는 것을 번 이상 반복하여 출구가 있는 방에 도달하면 승리한다.
번 방에 출구가 있는 경우, 게임이 시작할 때 앨리스가 있는 방에 출구가 있으므로 앨리스가 승리할 수 있음에 유의하라.
앨리스는 자신이 승리하기 위해서 최선을 다하며, 밥 역시 앨리스가 승리하지 못하게 하기 위해 최선을 다한다. 즉, 게임 중 밥이 어떤 선택을 하더라도 앨리스가 매 순간 적절한 선택을 하여 항상 출구가 있는 방에 도달할 수 있다면 앨리스가 승리하고, 그렇지 않으면 승리할 수 없다.
각 게임에 대해, 앨리스가 게임에서 승리할 수 있을지 아닐지를 판정하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 정수 에 대하여, 는 또는 이다.
- 정수 에 대하여
- 서로 다른 두 정수 , 에 대하여, 또는 이다.
- 정수 에 대하여
- 정수 에 대하여
- 정수 에 대하여
부분문제
- (6점) ; 정수 에 대하여, 와 을 만족한다. 출구는 번 방에만 존재한다. 즉, 과 을 만족한다.
- (8점) ; 정수 에 대하여, 과 을 만족한다.
- (7점)
- (14점)
- (15점)
- (16점) ; ; 정수 에 대하여
- (34점) 추가 제약 조건 없음.
입력 형식
첫 줄에 미로의 방의 수를 나타내는 정수 , 통로 종류의 수를 나타내는 정수 , 앨리스와 밥이 진행할 게임의 수를 나타내는 정수 가 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 개의 정수 이 공백으로 구분되어 차례대로 주어진다.
그다음 개의 줄에 걸쳐, 통로에 대한 정보가 주어진다. 이 중 번째 줄에는 세 정수 , , 가 공백으로 구분되어 차례대로 주어진다. 이는 미로에 번 방과 번 방을 연결하는 개의 통로가 있음을 의미한다.
그다음 개의 줄에 걸쳐, 앨리스와 밥이 진행할 번의 게임에 대한 정보가 주어진다. 이 중 번째 줄에는 두 정수 와 가 공백으로 구분되어 차례대로 주어진다.
출력 형식
첫 줄부터 개의 줄에 걸쳐, 답을 출력한다. 이 중 번째 줄에는 번째 게임에 대하여 앨리스가 승리할 수 있다면 YES, 그렇지 않다면 NO를 출력해야 한다.
예제
예제 1
5 5 5 0 0 1 0 0 1 2 1 1 3 1 1 4 2 2 3 2 3 4 1 2 1 1 2 3 3 4 4 5 1
YES YES YES NO NO
이 예제에서 미로에는 총 개의 방과 개의 통로가 있고, 출구는 번 방에만 있다. 앨리스와 밥은 총 번의 게임을 진행한다.
첫 번째 게임에서 앨리스는 처음에 번 방에 있고, 이동 시 개의 통로를 골라야 한다. 앨리스가 처음에 번 방으로 향하는 통로를 하나 고르면 밥도 같은 통로를 고르게 되고, 출구가 있는 번 방으로 이동하여 게임에서 승리할 수 있다.
두 번째 게임에서 앨리스는 처음에 번 방에 있고, 이동 시 개의 통로를 골라야 한다. 이때 앨리스는 다음과 같은 전략으로 게임에서 승리할 수 있다.
- 처음에 번, 번 방으로 향하는 통로를 하나씩 선택한다.
- 밥이 번 방으로 향하는 통로를 선택할 경우,
번 방에는 출구가 있으므로 앨리스가 승리한다.
- 밥이 번 방으로 향하는 통로를 선택했다 하자. 이때 앨리스가 번 방으로 향하는 통로를 개 고르면 밥은 두 통로 중 하나를 선택해야 하고, 앨리스가 번 방으로 이동하여 게임에서 승리한다.
따라서 앨리스는 밥의 선택과 무관하게 출구가 있는 번 방으로 이동하게 되어 게임에서 승리할 수 있다.
세 번째 게임에서 앨리스는 처음에 번 방에 있고, 이동 시 개의 통로를 골라야 한다. 번 방에는 출구가 있으므로, 앨리스는 아무 이동을 하지 않아도 승리한다.
네 번째 게임에서 앨리스는 처음에 번 방에 있고, 이동 시 개의 통로를 골라야 한다. 그러나 번 방과 연결된 통로는 번 방으로 향하는 것 개, 번 방으로 향하는 것 개로 총 개이다. 따라서 앨리스는 다른 방으로 이동할 수 없고, 게임에서 승리할 수 없다.
다섯 번째 게임에서 앨리스는 처음에 번 방에 있고, 이동 시 개의 통로를 골라야 한다. 번 방에는 출구가 없는데, 어떠한 통로도 연결되어 있지 않으므로 다른 방으로 이동할 수 없다. 따라서 앨리스는 게임에서 승리할 수 없다.
예제 2
4 3 4 1 0 0 0 1 2 2 2 3 3 3 4 1 1 3 2 2 3 3 4 1
YES YES NO YES
세 번째 게임에서 앨리스는 번 방에서 시작하고, 이동 시 개의 통로를 골라야 한다. 이때 밥이 다음과 같은 전략을 사용할 경우 앨리스는 승리할 수 없다.
- 앨리스가 처음에 번 방으로 향하는 통로를 하나라도 골랐다면, 밥은 그 통로를 선택한다. 그러면 앨리스는 번 방으로 이동하게 되는데, 번 방과 연결된 통로는 하나이므로 앨리스는 더 이상 이동할 수 없고, 게임에서 승리할 수 없다.
- 만약 앨리스가 번 방으로 향하는 통로를 고르지 않았을 경우, 가능한 상황은 번 방으로 향하는 통로를 세 개 고른 것이다. 이 경우 밥은 번 방으로 향하는 통로를 고르고, 앨리스는 번 방으로 이동한다.
- 번 방에서 연결되어 있는 통로 중 번 방으로 향하는 것은 개이므로, 앨리스는 이동을 위해 반드시 번 방으로 향하는 통로를 골라야 한다. 이때 밥도 번 방으로 향하는 통로를 선택하면 앨리스는 다시 번 방으로 이동하게 된다.
위 전략은 앨리스가 번 방으로 들어가기 전까지 계속하여 사용할 수 있다. 따라서 앨리스가 이동을 아무리 반복해도 출구가 있는 유일한 방인 번 방에 도달할 수 없고, 게임에서 승리할 수 없다.
예제 3
4 3 3 0 1 1 0 1 2 1 1 3 3 1 4 2 4 2 1 3 4 3
YES YES NO
예제 4
2 0 2 1 0 1 1 2 1
YES NO