백준 - 1600번 말이되고 싶은 원숭이 python 문제풀이 [Hellfer]

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

1600번: 말이 되고픈 원숭이

🔷 알고리즘 분류 - BFS(너비우선탐색), 난이도 - 골드 3

🔶문제 풀이 - BFS(너비우선탐색)을 이용한 풀이

from collections import deque

# 말처럼 움직일 때 이동하는 방향
dx1 = [-2, -1, 1, 2, 2, 1, -1, -2]
dy1 = [1, 2, 2, 1, -1, -2, -2, -1]

# 평범하게 움직일 때 이동하는 방향
dx2 = [-1, 0, 1, 0]
dy2 = [0, 1, 0, -1]

def bfs():
    queue = deque()
    queue.append((0, 0, 0)) # x, y, k
    visited[0][0][0] = True

    while queue:
        x, y, k = queue.popleft() # 큐에서 원소를 하나 꺼냄
        # 목표 위치에 도달했다면 이동 횟수를 반환
        if x == H-1 and y == W-1:
            return visited[x][y][k] - 1

        # 말처럼 움직일 수 있는 경우
        if k < K:
            for i in range(8):
                nx = x + dx1[i]
                ny = y + dy1[i]
                # 맵의 범위를 벗어나지 않고, 장애물이 없으며, 아직 방문하지 않았다면
                if 0 <= nx < H and 0 <= ny < W and not grid[nx][ny] and not visited[nx][ny][k+1]:
                    # 방문 표시를 하고 이동 횟수를 기록
                    visited[nx][ny][k+1] = visited[x][y][k] + 1
                    queue.append((nx, ny, k+1))

        # 평범하게 움직이는 경우
        for i in range(4):
            nx, ny = x + dx2[i], y + dy2[i]
            # 맵의 범위를 벗어나지 않고, 장애물이 없으며, 아직 방문하지 않았다면
            if 0 <= nx < H and 0 <= ny < W and not grid[nx][ny] and not visited[nx][ny][k]:
                # 방문 표시를 하고 이동 횟수를 기록
                visited[nx][ny][k] = visited[x][y][k] + 1
                queue.append((nx, ny, k))

    # 모든 경우를 다 확인했는데도 목표 위치에 도달하지 못했다면 -1을 반환
    return -1

K = int(input()) # 말처럼 움직일 수 있는 횟수
W, H = map(int, input().split()) # 맵의 가로 크기와 세로 크기
grid = [list(map(int, input().split())) for _ in range(H)] # 맵 정보
visited = [[[0]*(K+1) for _ in range(W)] for _ in range(H)] # 각 위치를 방문했는지 여부를 저장하는 리스트

print(bfs()) # bfs 함수를 호출하여 결과를 출력

🔶 초보자를 위한 생각주머니 키우기

🔸문제요약

이 문제는 체스판과 같은 2차원 그리드에서 시작점에서 도착점까지 이동하는데 필요한 최소 이동 횟수를

찾는 문제입니다. 이동은 상하좌우로 한 칸 움직이거나, 말처럼 대각선 방향으로 두 칸 이동한 후, 그 방향으로 90도 회전하여 한 칸 움직이는 두 가지 방법이 있습니다. 그리고 말처럼 움직일 수 있는 횟수가 제한되어 있습니다.

🔸해결전략

이 문제를 해결하기 위해서는 BFS(너비 우선 탐색) 알고리즘을 사용하는 것이 가장 효과적입니다.

BFS는 시작점에서 가장 가까운 노드부터 차례로 방문하는 방식으로, 이 문제에서는 말처럼 움직일 수 있는 횟수를 고려하여 최소 이동 횟수를 찾습니다.

🔸코드요약

코드는 크게 세 부분으로 이루어져 있습니다.

 

1. 초기 설정: 이동 방향, BFS 함수, 맵 크기, 맵 정보, 방문 여부를 저장하는 리스트 등을 설정합니다.

 

2. BFS 함수: BFS 알고리즘을 구현한 부분으로, 큐를 사용하여 말처럼 움직일 수 있는 횟수를 고려하면서 이동할 수 있는 모든 위치를 방문하고, 이동 횟수를 기록합니다.

 

3. 결과 출력: BFS 함수를 호출하여 최소 이동 횟수를 출력합니다. 즉, 이 코드는 BFS 알고리즘을 사용하여 말처럼 움직일 수 있는 횟수를 고려하면서 시작점에서 도착점까지의 최소 이동 횟수를 찾는 방법입니다.

 

🤗파이팅입니다~ 여러분!!🤗