너비우선탐색
-
[백준] 1068 트리 with PythonPS 2022. 7. 7. 22:19
📌 BOJ 1068 트리 💡 조건 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 문제. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다. 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울..
-
[백준] 14562 태권왕 with PythonPS 2022. 5. 12. 01:26
📌 BOJ 14562 태권왕 💡 조건 테스트 케이스의 수 C(1 ≤ C ≤ 100) 현재 점수 S와 T가 공백을 사이에 두고 주어진다. (1 ≤ S < T ≤ 100) 태균이가 현재 할 수 있는 연속 발차기는 두가지가 있다. A는 현재 점수만큼 점수를 얻을 수 있는 엄청난 연속 발차기이다. 하지만 상대 역시 3점을 득점하는 위험이 있다. B는 1점을 얻는 연속 발차기이다. 태균이의 점수 S와 상대의 점수 T가 주어질 때, S와 T가 같아지는 최소 연속 발차기 횟수를 구하는 문제 BFS(너비우선탐색) 유형의 문제 🖥 소스 코드 from sys import stdin from collections import deque def solve(s, t): q = deque() q.append((0, s, t)) ..
-
[백준] 2636 치즈 with PythonPS 2022. 3. 18. 17:58
📌 BOJ 2636 치즈 💡 조건 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈가 놓여 있다. 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. 입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 문제 세로와 가로의 길이는 최대 100이다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다. 너비우선탐색, BFS 유형의 문제 🖥 소..
-
[백준] 13565 침투 with PythonPS 2022. 2. 19. 18:10
📌 BOJ 13565 침투 💡 조건 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다. 맨 윗줄에서 받은 전기가 맨 밑 줄까지 갈 수 있다면 True, 아니면 False BFS 유형의 문제 🖥 소스 코드 from sys import stdin from collections import deque n, m = map(int, stdin.readline().split()) board = [] visited = set() for _ in range(n): board.append(list(map(int, list(stdin.readl..
-
-
[백준] 18352 특정 거리의 도시 찾기 with PythonPS 2021. 8. 30. 23:18
📌 BOJ 18352 특정 거리의 도시 찾기 💡 조건 및 풀이 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재. 모든 도로의 거리는 1. 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력. BFS 유형의 문제 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력 🖥 소스 코드 from sys import stdin from collections import deque n, m, k, x = map(int, stdin.readline().split()) graph = [[] for _ in range(n + 1)] for i in range(m): a, b = map(int, stdin.readl..