Beelog

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제는 위와 같으며, 일반적인 BFS 문제에 벽을 부수는 경우가 추가된 것입니다. 따라서 단순히 해당 위치를 방문했는지 여부를 확인하는 visited 배열을 [0, 0] 으로 만들어서 [벽을 부수지 않고 해당 위치를 방문한 경우 지나온 칸 수, 벽을 부수고 해당 위치를 방문한 경우 지나온 칸 수] 를 저장하는 형태로 생성합니다. 그리고 큐에 데이터를 저장할 때 [현재 위치의 x, 현재 ..

www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제는 위와 같고, Deque 를 사용하여 BFS 를 구현하는데 최단 거리를 구할 수 있는 지점을 알아야 하므로 방문했는지 확인하는 visited 배열을 boolean 형식이 아닌 int 형으로 만들어서 해당 인덱스에 이전에 방문했던 위치값을 넣는 방식으로 구현하였습니다. 파이썬 코드는 다음과 같습니다. from sys import stdin from collections im..

www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제는 위와 같으며, 이 문제는 시간당 물이 이동하는 경우와 고슴도치가 이동하는 경우를 나누어 BFS 방식을 통해 고슴도치가 비버 굴로 이동하는 최소 시간을 구하면 되는 문제입니다. 1. 숲의 정보를 이차원 배열에 저장하고, 이때 고슴도치의 출발 위치와 물의 위치(여러 개일 수 있으므로 배열에 저장)를 각각 저장합니다. 2. BFS 메소드를 수행하여 고슴도치가 안전하게 비버 굴에 도착할 수 있는 시간을 구합니다. (도착할 ..

www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제는 위와 같으며, 주어지는 층수 정보를 각각 변수에 저장한 뒤 시작 위치부터 위, 아래로 이동하는 경우를 확인하며 BFS 방식을 통해 문제를 해결할 수 있습니다. 파이썬 코드는 다음과 같습니다. from sys import stdin import heapq # 처음 위치부터 위, 아래로 이동하여 도착 위치에 도달할 때까지 누른 버튼 수 반환 def bfs(start): queue = [] heapq.heappush(qu..

www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 문제는 위와 같으며 BFS 를 통해 문제를 해결할 수 있습니다. 1. 먼저 정육면체 단위로 공간 정보가 주어지므로 3차원 배열을 사용하여 건물 내 칸 정보 (#, ., S, E) 를 저장합니다. 2. 건물 내 정보를 저장할 때 S, E 의 위치는 따로 저장합니다. 3. 시작 위치 S를 BFS 함수에 넘겨 출구 위치 E 까지 이동하는데 걸리는 시간을 반환하도록 합니다. 4. 해당 시간이 0이 아닌 경우 탈출이 가능한 ..