[ BOJ / 파이썬 ] 7562 나이트의 이동

/ 제출 1 /

# 22.08.17 24분간 풀어본 망한 풀이(무한 재귀)
import sys
input = sys.stdin.readline
from collections import deque


# 8가지
dx = [-2, -1, 1, 2, -1, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

tc = int(input())
for i in range(tc):
  l = int(input())
  board = [[0] * l for _ in range(l)]
  currentX, currentY = map(int, input().split())
  targetX, targetY = map(int, input().split())
  q = deque([(currentX, currentY)])
  while q:
    x, y = q.popleft()
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      
      if 0<= nx < l and 0<= ny < l:
        if board[nx][ny] >= 1:
          board[nx][ny] = min(board[nx][ny], board[x][y]+1)
        else:
          board[nx][ny] = board[x][y]+1
        
        q.append([nx, ny])
    
  print(board[targetX][targetY])

: 바로 틀렸습니다일 줄 알았는데 의외로 33퍼까지는 갔다가 메모리 초과가 나네요.. 에러인가.

: 거의 다 온 것 같은데, 못 찾겠네요. 애초에 로직이 부실해서인가봅니다.

: 하여간 무한루프 도는 풀이에서 더 아이디어를 떠올리는 사고력을 못 갖춘 것 같아서 풀이 보고 익히려 합니다. 

 

/ 제출 2 /

import sys

input = sys.stdin.readline
from collections import deque

# 8가지
dx = [-2, -1, 1, 2, -1, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

tc = int(input())
for _ in range(tc):
    l = int(input())
    board = [[0] * l for _ in range(l)]
    currentX, currentY = map(int, input().split())
    targetX, targetY = map(int, input().split())

    if currentX == targetX and currentY == targetY:
        print(0)
        continue

    q = deque([(currentX, currentY)])
    while q:
        x, y = q.popleft()
        if x == targetX and y == targetY:
            break
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < l and 0 <= ny < l:
                #if board[nx][ny] >= 1:
                #  board[nx][ny] = min(board[nx][ny], board[x][y]+1)
                if board[nx][ny] == 0:
                    board[nx][ny] = board[x][y] + 1
                    q.append((nx, ny))

    print(board[targetX][targetY])

: 아니 그래도 33퍼에서 틀리네요.. 뭐지.ㅠㅜ

 

 

/  제출 3  /

import sys

input = sys.stdin.readline
from collections import deque

# 8가지
dx = [-2, -1, 1, 2, -2, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

tc = int(input())
for _ in range(tc):
    l = int(input())
    board = [[0] * l for _ in range(l)]
    currentX, currentY = map(int, input().split())
    targetX, targetY = map(int, input().split())

    if currentX == targetX and currentY == targetY:
        print(0)
        continue

    q = deque([(currentX, currentY)])
    while q:
        x, y = q.popleft()
        if x == targetX and y == targetY:
            break
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < l and 0 <= ny < l:
                #if board[nx][ny] >= 1:
                #  board[nx][ny] = min(board[nx][ny], board[x][y]+1)
                if board[nx][ny] == 0:
                    board[nx][ny] = board[x][y] + 1
                    q.append((nx, ny))

    print(board[targetX][targetY])

: 세상에.. dx, dy 리스트에서 오타가 났을 거라고는 진짜 상상도 못하고 계속 로직만 고치고 있었습니다.

수정 전

수정 후

꼼꼼하게.

 

 

일단 이 문제에서 생각해볼 것.

 

1. 이동하며 값을 누적해가는 것은 BFS로 풀 수 있었다.

2. 값의 이동 거리가 1칸이 아니라 2칸 이상씩 그리고 (x,y)값에 따라 이동할 때는 경우의 수에 따라 dx, dy로 경우마다 리스트를 만들면 되는 것이었다. (이건 3차원 경우도 이렇게 하더라.) (=> 쫄지말자 그러니까. 꼭 1칸씩 움직이지 않을 때도 있다는 것 인지하자. )

3. while문에서는 끝나는 종료조건 꼭 정확하게 정의해야 멈춘다. 값이 틀리더라도 일단 이 정의를 해주는 것만은 잊지 말자. 무한 재귀는 최악이다.

4. 이동 거리를 구하는 BFS에서 방문 처리는 위와 같이 초기값0인 경우를 방문 안 한 값이라고 인지하게 했다. queue에서 꺼낸 값은 0일 수도 아닐 수도 있는 것. 다만 그 값을 기준으로 8가지 방면 돌면서 아직 안 간 곳에 현재의 값에 1 더한 수를 넣어줄 뿐. 

4-1. 4의 과정에서 최소값을 따로 구해야 한다고 생각했었다. 그런데 이동거리에 대한 BFS문제에서 그 부분은 굳이 필요가 없다. 첫 방문일 때가 가장 짧은 거리라고 가정하기 때문. 이게 해당 파트의 포인트.