728x90 BFS 썸네일형 리스트형 [백준알고리즘] 2186번: 문자판 -Python [백준알고리즘] 2186번: 문자판 -Python https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다. www.acmicpc.net 일단 파이썬보다는 PyPy로 통과할 확률이 높다. 이번 문제에서도 BFS 혹은 DFS를 통해서 주어진 문자열을 모두 완성할 수 있는 경우의 수를 구해주면 된다고 생각했다. 처음에는 이전에 몇 번 풀었던 것처럼 방문 여부를 확인하는 vis.. 더보기 [백준알고리즘] 2251번: 물통 -Python [백준알고리즘] 2251번: 물통 -Python https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다. 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. www.acmicpc.net 이번 문제에서도 visit을 딕셔너리로 사용했다. 그리고 (A, B, C)에 존재하는 물의 양.. 더보기 [백준알고리즘] 1525번: 퍼즐 -Python [백준알고리즘] 1525번: 퍼즐 -Python https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 보다시피 시간제한과 메모리 제한이 심한 문제이다. 처음 보고는 문제를 어떻게 풀어야 하나 캄캄했다... 일반적인 BFS방식으로는 불가능할 것 같고, 방문 유무를 체크해줌으로써 중복을 제거해야 하는데, 3x3크기의 배열을 어떻게 전체적인 모양을 가지고 방문 여부를 표시할 수 있을까 고민했다. 결국에 질문 게시판들을 보고 깨우치게 되었다. 조금만 더 쫄지않고 생각해봤으면 나왔을 수도 있지 않았을까 하는 아쉬움이 있다. 질문 게시판.. 더보기 [백준알고리즘] 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 와 이 문제도 되게 오래 걸려서 풀었다... 오래 걸린 이유는 두 가지로 뽑을.. 더보기 이전 1 2 3 4 다음
