dfs
-
[백준] 24480 알고리즘 수업 - 깊이 우선 탐색 2 with PythonPS 2023. 4. 10. 17:23
📌 BOJ 24480 알고리즘 수업 - 깊이 우선 탐색 2 💡 조건 N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자. 깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 내림차순으로 방문한다. 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u..
-
[백준] 1520 내리막 길 with PythonPS 2022. 6. 10. 15:44
📌 BOJ 1520 내리막 길 💡 조건 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오. 첫째 줄에는 지도의 세..
-
[백준] 20166 문자열 지옥에 빠진 호석 with PythonPS 2022. 6. 4. 01:36
📌 BOJ 20166 문자열 지옥에 빠진 호석 💡 조건 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다. 이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자. 너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다. 시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이..
-
[백준] 15658 연산자 끼워넣기 (2) with PythonPS 2022. 2. 2. 17:56
📌 BOJ 15658 연산자 끼워넣기 (2) 💡 조건 N개의 수로 이루어진 수열 A1, A2, ..., AN N(2 ≤ N ≤ 11), (1 ≤ Ai ≤ 100) 입력 값중 셋째 줄에 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 나눗셈은 정수 나눗셈으로 몫만 취한다. 또한 음수를 나눌 때에는 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾸어야 한다. 백트래킹, DFS 알고리즘 유형의 문제 🖥 소스 코드 from sys impo..
-
[백준] 1094 막대기 with PythonPS 2022. 2. 1. 02:14
📌 BOJ 1094 막대기 💡 조건 64cm인 막대를 가지고 있다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다. 아래는 막대를 자르는 방법이다. 1) 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다. 1-1) 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다. 1-2) 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.2) 이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다. X는 64보다 작거나 같은 자연수 DFS, 수학,..
-
[백준] 14502 연구소 with PythonPS 2022. 1. 24. 20:28
📌 BOJ 14502 연구소 💡 조건 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8) 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다. DFS + BFS, 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin from collections import deque n, m = map(int, stdin.readline()...