백준 5213 과외맨 (파이썬)

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

5213번: 과외맨

1. 홀수 행에서 이동할 때와 짝수 행에서 이동할 때를 고려해서 bfs 이동 방향 dx, dy를 2개 만든다

2. 지도를 만드는데 문제 조건대로 홀수 행의 마지막은 비워둔다

3. 지도의 각 칸에 번호를 매기는데 홀수 행의 마지막은 건너뛴다

4. 방문 확인 리스트 c와 어느 좌표로 부터 이동했는지 기록하는 dir 리스트를 만든다

5. bfs로 시작지점에서 이동을 시작한다

   현재 행의 홀짝여부와 앞의 칸과 뒤의 칸을 비교하는 조건을 모두 고려해서 설계한다

6. 이동 가능할 때, dir에 현재 좌표인 [x, y] 를 저장한다

7. 모든 이동을 끝내면 지도의 맨 끝에서부터 방문한 좌표를 찾는다

8. 이동횟수를 출력하고 ans에는 이동 경로를 저장한다

   dir 리스트에 저장한 좌표를 계속 불러오면 경로를 알 수 있다

9. 경로가 역순이므로 reverse한 후 하나씩 출력한다

from collections import deque
import sys


input = sys.stdin.readline
dx1 = [-1, 0, 1, 1, 0, -1]
dy1 = [1, 1, 1, 0, -1, 0]
dx2 = [-1, 0, 1, 1, 0, -1]
dy2 = [0, 1, 0, -1, -1, -1]


def bfs(x, y):
    q.append([x, y])
    c[x][y] = 1
    while q:
        x, y = q.popleft()
        if x % 2 == 1:
            dx, dy = dx1, dy1
        else:
            dx, dy = dx2, dy2
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if c[nx][ny] == 0:
                    if i <= 2:
                        if a[x][y][1] == a[nx][ny][0]:
                            c[nx][ny] = c[x][y] + 1
                            dir[nx][ny] = [x, y]
                            q.append([nx, ny])
                    else:
                        if a[x][y][0] == a[nx][ny][1]:
                            c[nx][ny] = c[x][y] + 1
                            dir[nx][ny] = [x, y]
                            q.append([nx, ny])


n = int(input())
a = [[[[] for _ in range(2)] for _ in range(n)] for _ in range(n)]
for i in range(n):
    if i % 2 == 0:
        for j in range(n):
            x, y = map(int, input().split())
            a[i][j] = [x, y]
    else:
        for j in range(n-1):
            x, y = map(int, input().split())
            a[i][j] = [x, y]

label = [[[] for _ in range(n)] for _ in range(n)]
num = 0
for i in range(n):
    for j in range(n):
        if i % 2 == 1 and j == n-1:
            continue
        num += 1
        label[i][j] = num

q = deque()
c = [[0]*n for _ in range(n)]
dir = [[[] for _ in range(n)] for _ in range(n)]
bfs(0, 0)

flag, ans = 0, []
for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if c[i][j]:
            print(c[i][j])
            ans.append(label[i][j])
            x, y = i, j
            while x > 0 or y > 0:
                nx, ny = dir[x][y]
                ans.append(label[nx][ny])
                x, y = nx, ny
            flag = 1
            break
    if flag:
        break
ans.reverse()
for s in ans:
    print(s, end=' ')