본문 바로가기

DFS

 (17)
[백준 / BOJ] 2251 물통 (cpp) 문제 출처 : https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 각각 부피가 A, B, C인 물통이 있고 A, B는 비어있으며 C는 꽉 차있다. 물을 이동 시킬때는 항상 하나의 물통이 꽉차거나 빌때까지만 옮길 수 있다. 이때, 물통 A가 비어있을때, 물통 C에 있을수 있는 물의 양을 모두 구하는 문제다. 풀이 DFS로 풀어도 풀리는 문제다. A, B, C의 최대 용량이 각각 200이므로, 3차원 체크 배열로 이미 방문한 상태를..
[백준 / BOJ] 14442 벽 부수고 이동하기 2 (Java) 문제 출처 : https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net N*M크기의 맵이 있고, 이 맵은 벽과 땅으로 이루어져있다. 벽을 부술수있는 횟수 K가 주어질때, K번 이하로 벽을 부수면서 (N,K)지점에 도착하는 최소 거리를 구하는 문제다. 풀이 BFS에 3차원 체크배열로 재방문을 잡아내며푸는 문제였다. 체크배열을 3차원으로 지정해야하는 이유는, (y,x)지점에 도달했을때, 벽을 A+1번 부순횟수보다 A번 부..
[백준 / BOJ] 19542 전단지 돌리기 문제 출처 : https://www.acmicpc.net/problem/19542 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이는 KENNYSOFT위치에서 시작하여 전단지를 다 돌리고 KENNYSOFT로 돌아오며, 이때, 전단지를 던져 거리가 D미만인 노드에 전단지를 한번에 돌릴 수 있다. 현민이가 전단지를 모든 노드에 돌리고 KENNYSOFT로 돌아오는 최단 경로를 구하는 문제다. 풀이 트리탐색으로 풀리는 문제였다. 1년전에 풀려고..
[백준 / BOJ] 1240 노드사이의 거리 문제 출처 : https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net N개의 노드로 이루어진 트리가 주어지고, M개의 쿼리가 주어질때, 노드 사이의 거리를 구하는 프로그램을 만드는 문제다. 풀이 트리 + 완전탐색 문제다. N이 1000, M이 1000으로, 한번탐색할때마다 최대 1000번 반복한다고 가정했을때, 최악의경우, 1000*1000번 반복하므로 시간복잡도는 O(NM)이 된다. 트리구조를 만든다음에 A위치에서 시작했을때, B위치에 도달했을때의 거리를 구하면된다. 거리구하는 소스코드 priv..
[백준 / BOJ] 5827 What's Up With Gravity 문제 출처 : https://www.acmicpc.net/problem/5827 5827번: What's Up With Gravity Output Details The captain starts at position (4, 2). She flips gravity and falls to position (2, 2) and then moves right twice to arrive at (2, 4). She flips gravity again and falls to position (4, 4) and then moves right once to position (4, 5). Finally www.acmicpc.net 캡틴 보비디안은 그녀의 선원 닥터 비팔로를 찾으러 모험을떠난다. 캡틴 보비디안이 도착한 세계..
[백준 / BOJ] 5852 Island Travels (Java) 문제 출처 : https://www.acmicpc.net/problem/5852 5852번: Island Travels Farmer John has taken the cows to a vacation out on the ocean! The cows are living on N (1
[백준 / BOJ] 18500 미네랄 2 (Java) / 2933 미네랄 1 포함 미네랄 2 기준으로 설명을 하겠다. (미네랄 1(2933번)과 2는 동일한 문제인데, 미네랄1이 테스트케이스가 좀더 빡샌거로 알고있다.) 실제로 동일 코드를 제출하면 모두 맞았습니다가 나온다. 문제 출처 : https://www.acmicpc.net/problem/18500 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 창영이와 상근이가 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 던져 싸우고있는데, 막대기가 날아가다 미네랄을 만나면, 해당 미네랄은 파괴되고 막대기도 이동을 멈춘다. 이때, 해당 미네랄이..
[백준 / BOJ] 1445 일요일 아침의 데이트 (Java) 문제 출처 : https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 형택이는 여자친구와 데이트를 하려고한다. 자신의 여자친구는 쓰레기를 지나가는것과, 쓰레기 주위를 지나가는것을 굉장히 싫어하기 때문에, 형택이는 이러한 상황을 최대한 피하고자한다. 숲의 크기 n,m 쓰레기의 위치(g), 형택이의 위치(S), 도착위치(F)가 주어진다. 이때, 위와 같은 상황을 최소화 하여 움직였을때 쓰레기를 지나간 횟수와 쓰레기 주위를 지나..

티스토리툴바