흙금이네 블로그

아이디어 BFS로 공주에게 도달하는 최단 시간을 구하고, T시간 이내에 도달할 수 있는지 확인한다. 풀이 #1 (Python) 방문 표시 및 각 칸에 도달하는 최단 시간 저장을 위해 N×M 크기의 0으로 채워진 2차원 리스트 visited를 생성한다. 출발 위치는 성의 구조 castle에서 1로 저장하여 다시 방문하지 않도록 하고, 도착 위치는 visited에서 T+1로 저장한다. 큐 queue에 출발 위치를 저장하고 while문에서 delta를 통해 BFS로 성을 탐색한다. 다음 칸이 도착 위치인 경우 도달 시간을 최솟값을 저장하고 큐 queue를 비운 후 break로 while문을 종료한다. 다음 칸이 도착 위치가 아니고 방문하지 않은 칸이라면 elif문으로 진입한다. 방문하는 칸이 빈 공간이라면 방..

아이디어 BFS로 1번 헛간과 거리가 가장 먼 헛간들을 찾는다. 풀이 #1 (Python) 방문 표시 및 1번 헛간과의 거리를 저장하기 위해 N+1 크기의 0으로 채워진 리스트 visited를 생성한다. visited에서 1번 헛간의 값을 1로 저장하고, 큐 queue에 1을 저장한다. while문에서 BFS로 방문하지 않은 주변 헛간으로 이동하며 visted에 1번 헛간과의 거리보다 1 더 큰 값을 저장한다. 모든 헛간을 방문한 후 for문에서 숨어야 하는 헛간 번호 num, 해당 헛간까지의 거리 d, 같은 거리의 헛간 수 cnt를 구한다. import sys input = sys.stdin.readline def solution(): N, M = map(int, input().split()) grap..

아이디어 BFS로 나이트가 체스판의 각 칸에 방문하기 위한 최소 이동 횟수를 구한다. 풀이 #1 (Python) 나이트가 이동할 수 있는 위치의 변화 값을 튜플로 리스트 delta에 저장한다. 체스판 내 각 칸의 최소 이동 횟수를 저장하기 위해 (N+1)×(N+1) 크기의 0으로 채워진 2차원 리스트 visited를 생성한다. visited에서 나이트의 초기 위치를 1로 저장하고, 큐 queue에 나이트의 초기 위치를 저장한다. while문에서 BFS로 나이트가 이동할 수 있는 칸으로 이동하며 visted에 최소 이동 횟수를 저장해 나간다. 체스판의 모든 칸에 대해 최소 이동 횟수를 저장한 후, for문에서 상대편 말을 잡기 위한 최소 이동 횟수들을 출력한다. import sys input = sys.s..