99클럽 코테 스터디 9일차 TIL: 재귀 함수로 구현하는 그래프

오늘의 문제 | 7562. 나이트의 이동

오늘 문제는 짧지만, 난이도는 확실히 있어보인다. 머리로 생각하기 보단 코드를 짜기가 어렵지 않을까하는 생각이 든다. 우선 생각없이 코드 구조부터 구성해봤다.

오늘은 확실히 아이디어가 쉽게 떠오르지 않는다. 단순히 BFS로 하자니 경우의 수가 너무 많아지고, 줄이자니 예외가 너무 많을 것처럼 느껴졌다. 확실히 실버1로 올라가니 체감 난이도가 오르긴 했다. 무지성으로 BFS를 짜보면 뭐라도 나오지 않을까.

아이디어: 미리 갈 수 있는 모든 곳까지의 거리를 계산해놓자.

사실 숫자가 그리 크지 않고, 체스판이 그리 크지 않기에 이론상 가능할 것이라 생각했다. 나이트가 움직일 수 있는 방법을 미리 리스트로 만들고, zip을 통해 새로운 위치에 대해 계속해서 체크하는 방식으로 했다.

# 정답 코드
from collections import deque

t=int(input())
move=[[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1]]

for _ in range(t):
    n=int(input())

    visit=[[-1 for i in range(n+1)] for i in range(n+1)]
    now=[*map(int,input().split())]
    goal=[*map(int,input().split())]
    idx=0

    deq=deque()
    deq.append(now)
    visit[now[0]][now[1]]=idx

    while deq:
        node=deq.popleft()
        idx=visit[node[0]][node[1]]
        for i in move:
            next=[x+y for x,y in zip(node,i)]
            if next[0]<0 or next[0]>=n: continue
            if next[1]<0 or next[1]>=n: continue
            if visit[next[0]][next[1]]!=-1: continue
            else: 
                visit[next[0]][next[1]]=idx+1
                deq.append(next)
    
    print(visit[goal[0]][goal[1]])

오늘의 회고

사실 처음에 내가 문제만 보고 쫄았던게 아닐까 싶다. 실버1 그래프 문제를 제대로 풀어본 기억이 별로 없기도 하고, 딱봐도 어렵게 생겨서 그냥 힌트를 보려고 했으나 생각보다 복잡한 사고를 요구하진 않아서 무리 없이 풀어냈다. 그래프 문제들을 열심히 연습하자…

사실 처음에는 재귀함수를 이용하면 빠르게 할 수 있지 않을까 했는데, 막상해보니 아니라는 것을 깨달았다. 실버 수준의 그래프는 구현 형태가 크게 달라지지 않는다. 재귀 함수를 이용하려면 BFS가 아닌 DFS를 이용해야 하는데, 이런 문제처럼 거리 구하는 문제는 BFS가 압도적으로 쉬운듯 하다.