[백준][Python] 18404 현명한 나이트

# 문제 링크

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

 

# 문제

NxN 크기 체스판의 특정한 위치에 하나의 나이트가 존재한다. 이때 M개의 상대편 말들의 위치 값이 주어졌을 때, 각 상대편 말을 잡기 위한 나이트의 최소 이동 수를 계산하는 프로그램을 작성하시오.
나이트는 일반적인 체스(Chess)에서와 동일하게 이동할 수 있다. 현재 나이트의 위치를 (X,Y)라고 할 때, 나이트는 다음의 8가지의 위치 중에서 하나의 위치로 이동한다.

(X-2,Y-1), (X-2,Y+1), (X-1,Y-2), (X-1,Y+2), (X+1,Y-2), (X+1,Y+2), (X+2,Y-1), (X+2,Y+1)

N=5일 때, 나이트가 (3,3)의 위치에 존재한다면 이동 가능한 위치는 다음과 같다. 나이트가 존재하는 위치는 K, 이동 가능한 위치는 노란색으로 표현하였다.

예를 들어 N=5, M=3이고, 나이트가 (2,4)의 위치에 존재한다고 가정하자. 또한 상대편 말의 위치가 차례대로 (3,2), (3,5), (4,5)라고 하자. 이때 각 상대편 말을 잡기 위한 최소 이동 수를 계산해보자. 아래 그림에서는 상대편 말의 위치를 E로 표현하였다. 단, 본 문제에서 위치 값을 나타낼 때는 (행,열)의 형태로 표현한다.

각 상대편 말을 잡기 위한 최소 이동 수는 차례대로 1, 2, 1이 된다.

 

# 입력

첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ X, Y ≤ N) 셋째 줄부터 M개의 줄에 걸쳐 각 상대편 말의 위치 (A, B)를 의미하는 A와 B가 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ A, B ≤ N)

단, 입력으로 주어지는 모든 말들의 위치는 중복되지 않으며, 나이트가 도달할 수 있는 위치로만 주어진다.

 

 

# 출력

첫째 줄에 각 상대편 말을 잡기 위한 최소 이동 수를 공백을 기준으로 구분하여 출력한다.

단, 출력할 때는 입력 시에 상대편 말 정보가 주어졌던 순서에 맞게 차례대로 출력한다.

 

# 예제

예제입력	예제출력
5 3 2 4 3 2 3 5 4 5	1 2 1

 

---

# 문제 풀이

https://github.com/taerimiiii/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/18404.%E2%80%85%ED%98%84%EB%AA%85%ED%95%9C%E2%80%85%EB%82%98%EC%9D%B4%ED%8A%B8

Algorithm/백준/Silver/18404. 현명한 나이트 at main · taerimiiii/Algorithm

 

엄청 복잡하지 않은 구현 + 그래프 탐색 문제다. dx dy 테크닉으로 풀어주었다. 테스트 케이스를 통과해서 제출했는데 틀렸다. 어떤 예외가 있을까 고민하다 틀린 케이스를 발견했다.

예제입력	예제출력	내 출력
5 4 2 4 3 2 3 5 4 5 1 1	1 2 1 2	1 2 1 4

 

    틀린코드    

import sys
input = sys.stdin.readline
from collections import deque

def in_range(x, y) :
    if 0 <= x < n and 0 <= y < n :
        return True
    return False

def bfs(x, y, target_map, visited, m) :
    queue = deque()
    queue.append([x, y])
    dxs, dys = [-2, -2, -1, -1, 1, 1, 2, 2], [-1, 1, -2, 2, -2, 2, -1, 1]
    loop_cnt = 0
    get_target_cnt = 0

    while get_target_cnt != m :
        length = len(queue)
        loop_cnt += 1

        for _ in range(length) :
            x, y = queue.popleft()

            for direct in range(8) :
                nx, ny = x + dxs[direct], y + dys[direct]
                
                if in_range(nx, ny) and not visited[nx][ny] :
                    visited[nx][ny] = True
                    if target_map[nx][ny] == 1 :
                        get_target_cnt += 1
                        target_map[nx][ny] = loop_cnt
                    else :
                        queue.append([nx, ny])  # 오류를 일으키는 부분
    return target_map


n, m = map(int, input().split())
x, y = map(int, input().split())
targets = [ list(map(int, input().split())) for _ in range(m) ]

target_map = [ [0] * n for _ in range(n) ]
for i in range(m) :
    a, b = targets[i]
    target_map[a-1][b-1] = 1

visited = [ [False] * n for _ in range(n) ]
visited[x-1][y-1] = True

target_map = bfs(x-1, y-1, target_map, visited, m)

for i in range(m) :
    a, b = targets[i]
    print(target_map[a-1][b-1], end=' ')

 

타겟(상대편 말)을 찾았을 때는 '말을 잡은 경우'로 따로 처리를 해서 큐에 추가하지 않았는데, 말을 잡은 경우도 결국 '나이트가 해당 칸에 이동한 것' 이기 때문에 똑같이 큐에 추가해 주어야 했다. 이 부분을 고쳐주니 통과되었다! 자세한 코드 해설은 밑에 주석으로 달아두었다.

 

    맞은코드    

import sys
input = sys.stdin.readline
from collections import deque

# 범위 검사 함수
def in_range(x, y) :
    if 0 <= x < n and 0 <= y < n :
        return True
    return False

# 너비 우선 탐색 함수
def bfs(x, y, target_map, visited, m) :

    # 변수 선언
    queue = deque()
    queue.append([x, y])
    dxs, dys = [-2, -2, -1, -1, 1, 1, 2, 2], [-1, 1, -2, 2, -2, 2, -1, 1]
    loop_cnt = 0        # 나이트가 이동한 횟수
    get_target_cnt = 0  # 찾은 말의 개수

    # 말의 위치는 나이트가 도달 할 수 있는 위치만 주어지므로,
    # 찾은 말의 개수가 m개가 아닐 동안 반복
    while get_target_cnt != m :
        loop_cnt += 1       # 나이트 이동 횟수 연산
        length = len(queue) # 큐의 길이 = 이번 루프에서 나이트가 있는 위치의 수

        # 현재 큐의 개수만큼 탐색
        for _ in range(length) :
            x, y = queue.popleft()

            # 나이트가 이동 할 수 있는 8방향 탐색
            for direct in range(8) :
                nx, ny = x + dxs[direct], y + dys[direct]
                
                # 나이트가 이동한 위치가 범위를 벗어나지 않고,
                # 방문적한 적도 없으면
                if in_range(nx, ny) and not visited[nx][ny] :
                    visited[nx][ny] = True  # 방문 처리
                    queue.append([nx, ny])  # 큐에 삽입

                    # 나이트가 이동한 위치에 말이 있으면
                    if target_map[nx][ny] == 1 :
                        get_target_cnt += 1           # 찾음 처리
                        target_map[nx][ny] = loop_cnt # 해당 위치에 이동한 횟수 저장

    return target_map

# 입력 처리
n, m = map(int, input().split())
x, y = map(int, input().split())
targets = [ list(map(int, input().split())) for _ in range(m) ]

# 타겟(상대편 말)의 정보를 저장하는 2차원 리스트
target_map = [ [0] * n for _ in range(n) ]
for i in range(m) :
    a, b = targets[i]
    target_map[a-1][b-1] = 1

# 방문 여부를 관리하는 리스트
visited = [ [False] * n for _ in range(n) ]
visited[x-1][y-1] = True

# 너비 우선 탐색
target_map = bfs(x-1, y-1, target_map, visited, m)

# 출력 처리
for i in range(m) :
    a, b = targets[i]
    print(target_map[a-1][b-1], end=' ')