[실버 1] 16948번: 데스 나이트

Original Source: https://www.acmicpc.net/problem/16948

16948번: 데스 나이트

---

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

---

사고의 흐름

• 데스 나이트가 한 번 이동할 수 있는 모든 경우의 수가 6가지이므로, n번 이동할 수 있는 경우의 수는 6^n이다. 이게 Greedy일 리가 없다.
• 체스판의 모양에 맞춰서 2차원 List를 만들고, 각 칸에 대응하는 원소에 데스 나이트가 칸에 도달하기까지 움직인 횟수를 저장하면 되겠다. 그래서 만약 데스 나이트가 어떤 칸에 도달했는데 이미 그 칸에 더 낮은 횟수가 저장되어 있으면 더 탐색하지 않도록 처리해주면 된다.
• 일반적으로 알고 있는 체스판의 좌표계와 2차원 List의 좌표를 일치시키기 쉽지 않다. 많이 연습해야겠다.

 

• Logic은 맞는 것 같은데 시간 초과가 뜨네...불필요한 계산이 어느 부분에서 발생하는지 확인하자
• 애초에 도착 지점의 List에 숫자가 입력되면 바로 종료하면 되겠는데?
• 도착 지점으로 향하지 않는 방향으로 뻗어나가는 경우들을 쳐내야 하지 않을까?
• 다음 움직일 좌표가 현재 좌표와 도착 좌표 사이에 있는 경우만 생각하고, 나머지는 버리면 되겠다.
• 그런데 같은 x축 위의 점으로 움직이려면 위아래로 한칸씩은 움직여야 하네.

 

• 시간 초과, 메모리 초과가 계속 뜨네. 다른 사람 코드를 참고하자.
• 조건문이 많아서 탐색 시간이 오래 걸렸네...

내가 작성한 소스코드

from sys import stdin
from collections import deque


def bfs(x1, y1, x2, y2, board_size):
    if x1 == x2 and y1 == y2:
        return 0

    queue = deque()
    queue.append((x1, y1))
    move_cnt[x1][y1] = 0
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(len(dx)):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if (nx < 0 or nx > board_size-1) or (ny < 0 or ny > board_size-1):
                continue

            if (nx < min(x,x2) - 1 or nx > max(x,x2) + 1) or (ny < min(y,y2) or ny > max(y,y2)):
                continue

            if move_cnt[nx][ny] < move_cnt[x][y] + 1 and move_cnt[nx][ny] > -1:
                continue

            if move_cnt[x2][y2] > 0:
                return move_cnt[x2][y2]

            queue.append((nx, ny))
            move_cnt[nx][ny] = move_cnt[x][y] + 1

    return move_cnt[x2][y2]


n = int(stdin.readline().rstrip())
move_cnt = [[-1] * n for _ in range(n)]

r1, c1, r2, c2 = map(int, stdin.readline().split())

x1 = (n-1) - c1
y1 = r1
x2 = (n-1) - c2
y2 = r2

'''
directions
0 : (r-2, c-1)
1 : (r-2, c+1)
2 : (r, c+2)
3 : (r+2, c+1)
4 : (r+2, c-1)
5 : (r, c-2)
'''
dx = (+1, -1, -2, -1, +1, +2)
dy = (-2, -2, +0, +2, +2, +0)

print(bfs(x1, y1, x2, y2, n))

남이 작성한 소스코드

어제의 나보다 성장하기 님:
https://honggom.tistory.com/144

피드백

• 평면좌표 - 2차원 List Index 사이 변환 / x = j, y = (size-1) - i / i = (size-1) - y, j = x
• BFS 탐색 반복문 안에 조건문을 많이 넣으면 프로그램 자체의 시간 복잡도는 올라가지 않지만 논리 연산 처리 시간이 추가되어 프로그램 실행 시간이 증가한다. 최대한 조건문을 간결하게 만들자.
• 그래프의 원소를 예외 시 출력값으로 초기화하면 조건문을 작성하기 편리하다.