bfs. 방문 기록의 중요성

#7562번 나이트의 이동 https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

처음에 짠 코드

for _ in range(int(input())):
    N = int(input())
    now = list(map(int, input().split()))
    target = list(map(int, input().split()))

    dr = [1, 2, 1, 2, -1, -2, -1, -2]
    dc = [-2, -1, 2, 1, -2, -1, 2, 1]

    queue = [now]
    cnt = 0
    answer = 0
    while queue and answer == 0:
        tmp = []
        print(cnt)
        for r, c in queue:
            if [r, c] == target:
                answer = cnt
                break

            for i in range(8):
                nr, nc = r+dr[i], c+dc[i]
                if 0 <= nr < N and 0 <= nc < N:
                    print(tmp)
                    tmp.append([nr, nc])
        cnt += 1
        queue = tmp
    print(answer)

무난하게 패스할거라 기대했는데, 진짜 오래걸려서 접었다...

 

뭐가 문제인지 한참 고민하다가 다른 솔루션을 찾았다. (구글링)

 

for _ in range(int(input())):
    N = int(input())
    now = list(map(int, input().split()))
    target = list(map(int, input().split()))
    visited = [[0]*N for _ in range(N)]

    dr = [1, 2, 1, 2, -1, -2, -1, -2]
    dc = [-2, -1, 2, 1, -2, -1, 2, 1]

    queue = [now]
    visited[now[0]][now[1]] = 1
    while queue:
        r, c = queue.pop(0)
        if [r, c] == target:
            # print(r, c)
            print(visited[r][c]-1)
            break

        for i in range(8):
            nr, nc = r+dr[i], c+dc[i]
            if 0 <= nr < N and 0 <= nc < N and visited[nr][nc] == 0:
                queue.append([nr, nc])
                visited[nr][nc] = visited[r][c] + 1

방문기록을 안해줘서 나이트가 무한 뺑뺑이를 돌린게 문제였다...

 

미안...

 

그래프 탐색은 방문기록이 참 중요한듯 하다

뺑치지지말자