7. 그래프에 대하여 (백준 7562 파이썬)

접근법은 잡은 것 같지만.. 여전히 어려운 그래프..문제들.. 저 표들만 보면 일단 눈물이 나고..^^

그래도 재귀 Recursion Error 난거 말고는(그게 문제지만) 얼추 맞았어서 함께 올려본다..

실버도 이렇게 어려운데 골드는 어케 풀죠?ㅎㅎ 도전할 생각도 안드는중.. 실버는 한다면 될 것 같은 느낌이라도 나는데 약간 골드는 도전하고 싶지가 않다..ㅎ

 

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

7562번: 나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

---

일단 그래프 문제니까 dx dy로 갈 수 있는 방향 정의하고, visited 배열을 만들어 둔다. 각 상황에 따라 갈 수 있는 방향일 경우(보드 밖을 벗어나지 않음 & 이미 간 곳이 아님) 거기서 다시 탐색을 하도록 만들었다. 

이것이 결국 정답과 내 오답 모두의 골자인데, 내 코드가 Recursion Error가 나고, 정답 코드는 안 나는 핵심적 차이는 결국 재귀를 들어가서 여기서 정답을 갈 수 있는지를 미리 판단하느냐, 아니냐의 차이였다. 이게 보고도 큰 차이가 난다고? 억울해! 라고 생각했는데, 막상 디버깅 돌려보니까 어마무시한 차이가 나던..ㅎㅎ;;

import sys

N = int(sys.stdin.readline())

# 갈 수 있는 방향 수(좌상부터 시계방향)
dx = [-1, -2, -2, -1, 1, 2, 2, 1]
dy = [-2, -1, 1, 2, 2, 1, -1, -2]

def solution2(able, count):
    # 도착하면 탐색 종료
    if (tx, ty) in able:
        return count
    
    # 갈 수 있는 방향 모두 탐색
    temp = []
    for i in range(len(able)):
        for j in range(8):
            next_x = able[i][0] + dx[j]
            next_y = able[i][1] + dy[j]
            if 0 <= next_x < l and 0 <= next_y < l:
                if visited[next_x][next_y] == 0:
                    visited[next_x][next_y] = 1
                    temp.append((next_x, next_y))

    result = solution2(temp, count +1)
    if result > 0:
        return result
    # 없을 경우 이 방향 탐색 종료
    return 0

# RecursionError
def solution(cx, cy, count):
    # 도착하면 탐색 종료
    if cx == tx and cy == ty:
        return count
    
    # 갈 수 있는 방향 모두 탐색
    for i in range(8):
        next_x = cx + dx[i]
        next_y = cy + dy[i]

        if 0 <= next_x < l and 0 <= next_y < l:
            if visited[next_x][next_y] == 0:
                visited[next_x][next_y] = 1
                able.append((next_x, next_y))

    result = solution(able, count +1)
    if result > 0:
        return result
    # 없을 경우 이 방향 탐색 종료
    return 0


for _ in range(N):
    l = int(sys.stdin.readline())
    cx, cy = map(int, sys.stdin.readline().split())
    tx, ty = map(int, sys.stdin.readline().split())
    
    visited = [[0]*l for _ in range(l)]
    visited[cx][cy] = 1
    able = [(cx, cy)]
    print(solution2(able, 0))

• 재귀 가보기 전에 판단할 수 있는 것은 최대한 재귀 들어가지 않고 판단하도록 할 것
• 재귀 return은 아직도 헷갈린다. 이전에는 더 확실하게 알고 썼던 것 같은데 (return 값끼리 더해서 global안쓰고 count 가져가기 등) 지금은 이게 맞나.. 일단 return에 성공/실패를 나눠서 성공일 경우 아예 종료를 하고 싶었는데, 잘 된건지도 모르겠고 꼭 필요한 코드가 맞는지도 모르겠고..ㅎ 어렵다
• 그래도 그래프 기본 접근은 이제 알 것 같아서 다행이다.. 그래프 안나오는 코테는 없는듯..ㅎ