bfs
-
[백준 BOJ] 4179번 불! (파이썬 Python)코딩/알고리즘 - 백준 2025. 4. 3. 00:21
문제지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.불은 각 지점에서 네 방향으로 확산된다.지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.지훈이와 불은 벽이 있는 공간은 통과하지 못한다. https://www.acmicpc.net/problem/4179 풀이- BFS로 탐색 구현 (BFS 문제집에 있는 문제를 풀이 중 / 링크 )- 문제 입력 입력 - 지금까지와는 다른게 2가지 경우로 구분 (지훈과 불의 위치)- 지훈과 불의 좌..
-
[백준 BOJ] 2667번 단지번호붙이기 (파이썬 Python)코딩/알고리즘 - 백준 2025. 3. 19. 11:35
문제과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. https://www.acmicpc.net/problem/2667 풀이- BFS로 탐색 구현- 집(1)을 만났을때 BFS 실행- count를 더해주며 단지의 집의 수 계산 정답 코드import sysinput = sy..
-
[백준 BOJ] 7562번 나이트의 이동 (파이썬 Python)코딩/알고리즘 - 백준 2025. 3. 17. 11:33
문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?https://www.acmicpc.net/problem/7562 풀이- BFS로 최단경로 구현- 현재 위치(current)와 목표 위치(target) 설정- 한번 이동할 때마다 해당 위치에 +1- 목표 위치(target) 도달 시 graph의 값 반환 정답 코드from collections import dequeimport sysinput = sys.stdin.readlinet = int(input())for _ in range(t): L = int(input()) current = lis..