[BOJ 5213🥇2] 과외맨 (Python)

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

5213번: 과외맨

 

문제

과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다.

얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 동안 과외 노트를 훔쳐갔다. 과외맨은 빼앗긴 노트를 찾아오기 위해 인천 공항으로 가서 과테말라로 가는 비행기를 탔다.

일단 언어가 통하지 않기 때문에, 과외맨은 자신의 특기를 살려서 일주일간 과테말라에서 스페인어를 과외 받았다.

오랜 고서에 의하면, 고대 마야인은 하늘을 날아다니는 재주가 있었다고 한다. 과외맨은 매일 밤 하늘을 바라보며 마야인들의 흔적을 찾으려고 애를 썼다.

그렇게 한 달이 지났을까... 한국에선 이민혁 실종 사건이 연일 대서특필 되고 있고, 사람들은 사라진 과외맨을 찾으며 시청 광장에서 촛불 집회를 했다. 과외맨도 이런 사실에 안타까움을 느꼈다. 하지만, 과외 노트 없는 과외맨은 평범한 대학생과 같기 때문에 아직 돌아갈 수 없었다.

과외 노트의 단서는 뜻하지 않게 스페인어 과외를 받던 중에 알게 되었다. 과외맨의 과외 선생님이 주말을 이용해서 등산을 하던 사이에 고대 마야의 사원으로 보이는 것을 발견했고, 민혁이에게 과외 노트가 거기에 있는 것 같다고 알려주었다.

과외맨은 즉시 과외 노트를 찾으러 고대 마야의 사원으로 여행을 떠났다.

고대 마야의 사원의 입구로 들어간 과외맨은 매우 놀랐다. 바로 과외 노트가 자신의 눈 앞에 있는 것 이었다. 과외맨은 이적의 다행이다를 부르면서 과외 노트를 집으려고 했지만, 그것은 노트의 홀로그램이었다. 이어서 고대 마야인의 목소리가 사원을 가득 채우기 시작했다. 하지만, 고대 마야인은 스페인어를 사용하지 않았다. 과외맨은 닥터후에게 전화를 걸어서 자신에게 타디스의 번역 프로토콜을 제공해 줄 수 있는지를 물어 보았다. 닥터는 흔쾌히 요청을 받아들였고, 민혁이는 마야인의 메시지를 듣기 위해 밖으로 나갔다가 다시 들어왔다.

"하하하. 과외 노트를 돌려 받고 싶나? 그럼 여기로 와서 가져가 보시지. 하하하하"

과외맨의 과외 노트는 입구의 반대편에 있고, 그 사이에는 절벽이 있었다. 갑자기 하늘에서 거대한 도미노 타일이 떨어졌고, 그 사이를 연결하는 다리를 만들었다.

도미노 타일은 두 조각으로 나누어져 있었고, 각 조각은 정사각형이다. 조각에는 1과 6사이의 숫자가 써져 있다.

타일은 N줄로 놓여져 있고, 홀수 줄에는 N개의 타일이, 짝수 줄에는 N-1개의 타일이 놓여져 있다. 아래 그림은 (N=5)일 때 타일이 놓여져 있는 형태이다.

한 타일에서 다른 타일로 넘어가려면, 두 타일이 인접해야 한다. 또, 같은 변을 공유하는 조각에 쓰여 있는 숫자가 같아야 한다.

과외맨은 반대편으로 넘어가기 위해서 첫 줄의 가장 첫 타일에서 마지막 줄의 가장 마지막 타일로 이동하는 가장 짧은 경로를 찾으려고 한다.

타일은 row-major order에 의해서 번호가 매겨져 있으며, 첫 번째 줄의 첫 타일의 번호는 1, 마지막 타일의 번호는 N이다. 두 번째 줄에서 첫 타일의 번호는 N+1이고, 마지막 타일의 번호는 2*N-1이다.

첫 줄의 첫 타일로만 과외맨이 들어갈 수 있고, 마지막 줄의 마지막 타일위에 과외 노트가 놓여져 있다.

마지막 줄의 마지막 타일로 이동할 수 없는 경우가 존재할 수 있다. 이 경우에는 번호가 가장 큰 타일로 이동하면 된다.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄부터 N*N-N/2줄(/는 정수 나눗셈이다)에는 두 양의 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 6, 1 ≤ i ≤ N * N - N / 2) 타일 i의 왼쪽에 쓰여 있는 숫자는 Ai, 오른쪽에 쓰여 있는 숫자는 Bi이다.

 

출력

첫째 줄에 가장 짧은 경로의 길이 (타일의 개수)를 출력한다.

둘째 줄에는 경로 상의 타일의 번호를 공백으로 구분하여 순서대로 출력한다. 만약, 가장 짧은 경로가 여러 가지라면, 아무거나 출력하면 된다.

 

예제 입력 1

5
1 4
4 5
3 4
5 4
5 2
4 2
5 6
4 4
6 5
2 4
5 1
6 1
1 6
2 3
4 2
5 3
1 2
5 5
4 1
2 2
4 3
2 3
3 4

 

예제 출력 1

7
1 2 7 12 17 22 23

 

예제 입력 2

3
1 2
2 3
6 6
2 4
3 5
6 6
4 5
5 6

 

예제 출력 2 

4
1 2 5 8

 

예제 입력 3 

4
1 5
5 3
5 5
5 6
5 3
6 4
4 5
2 5
2 4
4 3
2 4
5 2
1 4
1 6

 

예제 출력 3 

7
1 5 8 12 9 10 13

 

⭕ CODE

from collections import deque


def bfs(x, y):
    q = deque()
    q.append((x, y))
    path[x][y] = 0

    while q:
        x, y = q.popleft()

        # 1,3,5번째 줄 index 때문에 짝수로 조건을 줌
        if x % 2 == 0:
            if 0 <= y < n:
                # 아래 왼쪽 아래 왼쪽은 y index가 하나 작다
                # 아래쪽이므로 y 인덱스는 n-2까지밖에 없다
                if 0 <= x + 1 < n and 0 <= y - 1 < n - 1 and arr[x][y][0] == arr[x + 1][y - 1][1] and path[x + 1][
                    y - 1] == 0:
                    q.append((x + 1, y - 1))
                    # 도착할 위치에 이전 위치를 담기
                    path[x + 1][y - 1] = (x, y)

                # 아래 오른쪽 (x+1,y) 아래 오른쪽은 y index가 같다
                # 아래쪽이므로 y 인덱스는 n-2까지밖에 없다
                if 0 <= x + 1 < n and 0 <= y < n - 1 and arr[x][y][1] == arr[x + 1][y][0] and path[x + 1][y] == 0:
                    q.append((x + 1, y))
                    path[x + 1][y] = (x, y)

                # 위 왼쪽 y인덱스가 하나 작다
                # 위쪽이므로 y 인덱스는 n-2까지밖에 없다
                if 0 <= x - 1 < n and 0 <= y - 1 < n - 1 and arr[x][y][0] == arr[x - 1][y - 1][1] and path[x - 1][
                    y - 1] == 0:
                    q.append((x - 1, y - 1))
                    path[x - 1][y - 1] = (x, y)

                # 위 오른쪽 y인덱스가 같다
                # 위쪽이므로 y 인덱스는 n-2까지밖에 없다
                if 0 <= x - 1 < n and 0 <= y < n - 1 and arr[x][y][1] == arr[x - 1][y][0] and path[x - 1][y] == 0:
                    q.append((x - 1, y))
                    path[x - 1][y] = (x, y)

                # 오른쪽
                if 0 <= x < n and 0 <= y + 1 < n and arr[x][y][1] == arr[x][y + 1][0] and path[x][y + 1] == 0:
                    q.append((x, y + 1))
                    path[x][y + 1] = (x, y)

                # 왼쪽
                if 0 <= x < n and 0 <= y - 1 < n and arr[x][y][0] == arr[x][y - 1][1] and path[x][y - 1] == 0:
                    q.append((x, y - 1))
                    path[x][y - 1] = (x, y)

        # 2,4,6번째 줄 index 때문에 홀수로 조건을 줌
        # n-1개의 타일만 존재
        else:
            if 0 <= y < n - 1:

                # 아래 왼쪽
                if 0 <= x + 1 < n and 0 <= y < n and arr[x][y][0] == arr[x + 1][y][1] and path[x + 1][y] == 0:
                    q.append((x + 1, y))
                    path[x + 1][y] = (x, y)

                # 아래 오른쪽
                if 0 <= x + 1 < n and 0 <= y + 1 < n and arr[x][y][1] == arr[x + 1][y + 1][0] and path[x + 1][
                    y + 1] == 0:
                    q.append((x + 1, y + 1))
                    path[x + 1][y + 1] = (x, y)

                # 위 왼쪽
                if 0 <= x - 1 < n and 0 <= y < n and arr[x][y][0] == arr[x - 1][y][1] and path[x - 1][y] == 0:
                    q.append((x - 1, y))
                    path[x - 1][y] = (x, y)

                # 위 오른쪽
                if 0 <= x - 1 < n and 0 <= y + 1 < n and arr[x][y][1] == arr[x - 1][y + 1][0] and path[x - 1][
                    y + 1] == 0:
                    q.append((x - 1, y + 1))
                    path[x - 1][y + 1] = (x, y)

                # 오른쪽
                if 0 <= x < n and 0 <= y + 1 < n - 1 and arr[x][y][1] == arr[x][y + 1][0] and path[x][y + 1] == 0:
                    q.append((x, y + 1))
                    path[x][y + 1] = (x, y)

                # 왼쪽
                if 0 <= x < n and 0 <= y - 1 < n - 1 and arr[x][y][0] == arr[x][y - 1][1] and path[x][y - 1] == 0:
                    q.append((x, y - 1))
                    path[x][y - 1] = (x, y)
    return path


n = int(input())

arr = []

# 이전에 어느 위치에서 왔는지 체크하기 위한 path
path = [[0] * (n - 1) for _ in range(n)]
# index를 확인하기 위한 check
check = [[0] * (n - 1) for _ in range(n)]

for i in range(n):
    if i % 2 == 0:
        arr.append(list([0, 0] for _ in range(n)))
        path[i].append(0)
        check[i].append(0)
    else:
        arr.append(list([0, 0] for _ in range(n - 1)))

# 입력값 받기
for i in range(n):
    if i % 2 == 0:
        for j in range(n):
            x, y = map(int, input().split())
            arr[i][j] = [x, y]
    else:
        for j in range(n - 1):
            x, y = map(int, input().split())
            arr[i][j] = [x, y]

# check 인덱스 담기
a = 1
for i in range(n):
    if i % 2 == 0:
        for j in range(n):
            check[i][j] = a
            a += 1
    else:
        for j in range(n - 1):
            check[i][j] = a
            a += 1

# bfs실행
bfs(0, 0)

# path n*n 으로 만들어서 탐색하기 편하게 만들어줌
for i in range(n):
    if i % 2 == 1:
        path[i].append(0)

# 순서를 찾기 위한 result
result = []


flag = 0

# 역순으로 탐색하기
for i in range(n - 1, -1, -1):
    for j in range(n - 1, -1, -1):
        # path[i][j]가 0이 아니라면 즉 갈 수 있다면
        if path[i][j] != 0:
            # result에 담기 
            result.append(check[i][j])
            x, y = i, j
            while True:
                # path[x][y] 가 0이 아니라면 즉 다른곳에서 x,y로 이동 왔다면
                if path[x][y] != 0:
                    # 그전 위치 nx,ny
                    nx = path[x][y][0]
                    ny = path[x][y][1]
                    x, y = nx, ny
                    # 그전 위치 result에 담기
                    result.append(check[x][y])
                # x,y가 (0,0)이라면 
                # 즉 이전위치가 출발점이라면 멈추기
                if x == 0 and y == 0:
                    flag = 1
                    break
            if flag:
                break
    if flag:
        break

result.reverse()

# result의 길이가 0이라면 불가능하므로
# 1
# 1
# 출력
if len(result) == 0:
    print(1)
    print(1)

# 그게 아니라면
else:
    # 최단 경로 길이 
    print(len(result))
    # 방문 순서 출력
    print(*result)

✏️ Comment

경로를 찾는 방법을 생각하는게 많이 어려웠다.
현재 위치에 이전에 어디에서 왔는지를 기록해두어 목적지부터 출발지까지 역순으로 찾아가는 형식을 사용했다.