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/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제는 위와 같으며, BFS 를 통해 문제를 풀 수 있습니다. 먼저 이 문제는 BFS 를 수행하는데 연결이 끝나려면 최종적으로는 사이클이 만들어져야 한다는 것입니다. 1 => 3 => 3 2 => 1 => 3 => 3 3 => 3 4 => 7 => 6 => 4 5 => 3 => 3 또한, 이미 1부터 시작하여 3을 확인하고 3이 사이클을 이룬다는 것을 확인한 뒤에는 2를 확인한 경우도 1까지 확인한 경우와 뒷부분 사..

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..