그래프탐색
-
[백준] 13459 구슬 탈출 with PythonPS 2022. 6. 3. 02:29
📌 BOJ 13459 구슬 탈출 💡 조건 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. N, M (3 ≤ N, M ≤ 10) 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다. 각각의 동작에서 공은 동시에 ..
-
[백준] 17839 Baba is Rabbit with PythonPS 2022. 5. 13. 15:55
📌 BOJ 17839 Baba is Rabbit 💡 조건 N(1 ≤ N ≤ 100,000) N개의 줄에 걸쳐 명령이 주어진다. 각 명령은 p is q의 형태로 주어지며, p와 q는 첫 글자가 영문 대문자이고, 나머지 글자는 영문 소문자인 길이 10 이내의 문자열이다. Baba에 명령을 한 번 이상 적용한 결과로 나올 수 있는 사물을 사전순으로 출력한다. 단, 적용할 수 있는 명령이 없다면, 아무것도 출력하지 않는다. 그래프 탐색, BFS 유형의 문제 🖥 소스 코드 from collections import deque from sys import stdin graph = {} for _ in range(int(stdin.readline())): a, b = stdin.readline().rstrip().s..
-
[백준] 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..