728x90 dfs 썸네일형 리스트형 [백준알고리즘] 9019번: DSLR -Python [백준알고리즘] 9019번: DSLR -Python https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경 www.acmicpc.net 이번 문제도 주어진 두 값 A, B 간의 제시된 4가지 이동 방법에 따라 만날 수 있.. 더보기 [백준알고리즘] 1963번: 소수 경로 -Python [백준알고리즘] 1963번: 소수 경로 -Python https://www.acmicpc.net/problem/1963 더보기 [백준알고리즘] 1697번: 숨바꼭질 -Python [백준알고리즘] 1697번: 숨바꼭질 -Python https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 처음에 이번 문제를 DFS 방식으로 풀으려 했다. 백트래킹으로 여러 조건들을 추가해서 .. 더보기 [백준알고리즘] 11725번: 트리의 부모 찾기 -Python [백준알고리즘] 11725번: 트리의 부모 찾기 -Python https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리의 연결 정보가 주어졌을 때 각 노드의 부모를 모두 출력하는 문제이다. 처음 주어진 입력 정보를 각 노드의 번호별로 리스트를 통해서 유지했다. 그 후 head[]라는 부모 노드의 번호를 가리키는 리스트를 생성해주었고, 1번 노드부터 BFS 방식으로 문제를 풀었다. 각 노드와 연결된 노드 중에서 아직 head[]에 부모 노드가 결정되지 않은 노드는 현재 노드를 부모로 하도록 해주었다. 사이클이 없.. 더보기 [백준알고리즘] 1167번: 트리의 지름 -Python [백준알고리즘] 1167번: 트리의 지름 -Python https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다) 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되 www.acmicpc.net 와 이 문제도 되게 오래 걸려서 풀었다... 오래 걸린 이유는 두 가지로 뽑을.. 더보기 [백준알고리즘] 1991번: 트리 순회 -Python [백준알고리즘] 1991번: 트리 순회 -Python https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다. www.acmicpc.net 이번 문제는 tree traversal (트리 순회) 문제이다. 트리 순회에는 문제에서 요구하는 데로 3가지 방법이 있다. 1. preorder traversal (전위 순회) 2. inorder traversal (중위 순회) 3. postor.. 더보기 [백준알고리즘] 2146번: 다리 만들기 -Python [백준알고리즘] 2146번: 다리 만들기 -Python https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북 www.acmicpc.net 와;;; 너무 어려웠다 ㅠㅠㅠ 문제를 푸는 방법은 그래도 찾았는데.. 계속 메.. 더보기 [백준알고리즘] 2178번: 미로 탐색 -Python [백준알고리즘] 2178번: 미로 탐색 -Python https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번 문제는 반드시 (1, 1)에서 (N, M)으로 가는 것이기 때문에 길만 따라가면 돼서 간단하게 해결했다. BFS로 문제를 풀었고, 이동한 각 지점에서 상하좌우를 큐에 넣어주었다. 큐에서 꺼낼 때 경곗값 검사를 진행해주었고, 해당 위치가 길이 맞는지 확인해주었다. import sys from collections import deque def bfs(): queue = d.. 더보기 이전 1 2 3 4 5 6 다음