과외맨 [5213] with 파이썬

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

5213번: 과외맨

출처: https://rebas.kr/733 [PROJECT REBAS]

 

 

• 우선 주어지는 입력 데이터를 2차원 인접 행렬로 변환한다. 하나의 타일은 2 조각으로 나누어져 있으므로, 세로 N개 가로 N*2개이다. 따라서 인접 행렬을 a[N][N*2]로 선언한다.
• 입력 데이터를 인접 행렬에 넣을 때, 홀수 줄, 짝수 줄에 따라 다르게 넣어야 한다. 홀수 줄에서는 2*N개의 데이터를 모두 넣는다. 짝수 줄에서는 앞뒤로 한 칸씩 0으로 비워놓고, 안쪽에 2*N-1개의 데이터를 넣는다. 데이터는 총 N*N-N/2줄에 2개씩 들어온다.
• 인접 행렬을 만들면서 각 타일의 레벨 값을 저장할 배열 b를 a와 같은 사이즈로 선언한다.
• b 배열은 a와 마찬가지로 홀수 줄과 짝수 줄을 구분해야 한다. 홀수 줄에는 N개의 레벨이 있고, 짝수 줄에는 N-1개의 레벨이 있다.
• a와 b 배열을 모두 만들었다면, 이를 바탕으로 인접 리스트 v를 생성한다. 하나의 타일에서 상하좌우로 탐색하면서 더 나아갈 수 있는 타일이 있다면, 그 타일에 인접 리스트로 연결한다.
• 넘어갈 수 있는 타일은, 같은 레벨일 경우와, 다른 레벨일 때 같은 숫자일 경우이다.
• 인접리스트 v를 바탕으로 BFS 탐색을 하고, BFS 탐색을 하면서 이동 경로를 저장한다.
• 이동 경로는 BFS 탐색을 진행하면서 현재 위치에 이전 위치를 넣으면서 저장할 수 있고, BFS 탐색 종료 후 역순으로 출력하면 된다.
• 마지막 도착 지점은 타일 레벨이 제일 큰 곳이므로, 이전에 저장한 레벨보다 큰 레벨에 도착할 때 업데이트하면 된다.

 

 

# 초기화 하는 부분 코드를 이해를 못해서 내가 아는 수준으로 수정했다.

# 파이썬3 채점시 시간초과.. -> Pypy3 로 하면 통과된다.

 

from collections import deque

n = int(input())
# t 값 + 1 -> 0번 배열 사용안하기 때문
m, t = n*2, n*n-n//2+1
# Adjacent matrix
a = [[0]*m for _ in range(n)]
# Level Map
b = [[0]*m for _ in range(n)]
# Adjacent List
v = [[] for _ in range(t)]
path = [0 for _ in range(t)]

# adjacent matrix
def init():
    temp = deque()
    temp2 = deque()
    for i in range(1, t):
        temp.extend(list(map(int, input().split())))
        temp2.extend([i] * 2)

    for i in range(n):
        for j in range(m):
            if i % 2 == 1 and (j == 0 or j == m - 1):
                a[i][j] = 0
                b[i][j] = 0
            else:
                a[i][j] = temp.popleft()
                b[i][j] = temp2.popleft()

# adjacent list
def graph():
    dirs = [(-1,0),(1,0),(0,-1),(0,1)]
    for i in range(n):
        for j in range(m):
            now = b[i][j]
            for di, dj in dirs:
                ni, nj = i+di, j+dj
                if ni < 0 or ni >= n or nj < 0 or nj >= m:
                    continue
                nxt = b[ni][nj]

                # nxt 와 now 의 레벨이 다르고 인접한 값이 같으면 근접 리스트에 추가
                if now != nxt and a[i][j] == a[ni][nj]:
                    v[now].append(nxt)

def bfs(ans):
    q = deque([1])
    check = [False]*t
    check[1] = True
    while q:
        x = q.popleft()
        for nx in v[x]:
            if not check[nx]:
                # 번호 중 가장 큰 것 저장
                ans = max(ans, nx)
                check[nx] = True
                # 새로운 경로 해당 레벨에 이전 경로 저장
                path[nx] = x
                q.append(nx)
    return ans

def result(ans):
    p = [ans]
    x = ans
    while path[x]:
        x = path[x]
        p.append(x)
    print(len(p))
    p.reverse()
    for i in p:
        print(i, end=' ')

init()
graph()
result(bfs(0))