알고리즘 | 음료수 얼리기 문제 (BFS와 DFS로 각각 풀어보기)
더보기 N by M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0 칸막이가 존재하는 부분은 1입니다. 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어 있는 것으로 판단합니다. 이러한 경우에서 얼음 틀의 모양이 그래프로 주어진다면 생성되는 아이스크림의 갯수는 몇 개일까요? graph_45 = [ [0,0,1,1,0], [0,0,0,1,1], [1,1,1,1,1], [0,0,0,0,0] ] n = 4 m = 5 첫째 / BFS 방식으로 풀기 출발점에서부터 점진적으로 진행해가는 방식으로 접근하는 경우 BFS를 고려해볼 수 있습니다. 일단 BFS니까 아묻따 디큐부터 임포트해주고 시작합니다. from collections import deque 1. 함수를 작성합니다. 입력받..
2024. 4. 2.
알고리즘 | BFS 활용하여 미로 찾기 문제 풀기
백준 2178번 미로탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net n = 4 m = 6 graph = [ [1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 1], [1, 1, 1, 0, 1, 1] ] 0과 1로 이루어진 n * m 크기의 미로 그래프가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동..
2024. 4. 1.
알고리즘 | BFS 활용하여 특정 도시 거리 계산 문제 풀기
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 ..
2024. 4. 1.
