본문 바로가기

dfs

Baekjoon 17070 파이프 옮기기 1 2019. 3. 12. Link https://www.acmicpc.net/problem/17070 소스결과 8516 KB / 104 ms 출처 Baekjoon 언어 C++ 17 분류 BFS DFS 설명 시작 지점에서 가로로 놓여있는 파이프를 연결해 목적지에 연결 할 수 있도록 파이프를 배치 하는 방법의 가지 수를 출력해주자. 이번 삼성 A형 1번 문제에서 몇가지 조건이 빠진 문제다. 나머지 조건은 똑같다. 크게 다른 점이라면 문제가 조금 친절한 점 정도일까.. 파이프를 놓을 수 있는 방법은 3가지 존재한다. 그리고 파이프를 연결 하는 부분에 있어서 45도 이상 돌릴 수 없다. 가로로 놓인 파이프 뒤에 바로 세로를 놓을 수는 없다. 가로와 세로로 놓을 때에는 칸만 조사하지만, 대각선으로 놓는 경우는 3칸을 조사 해야한다. 시작..
BaekJoon 6593 상범 빌딩 2019. 2. 3. Link https://www.acmicpc.net/problem/6593 소스결과 1988 KB / 4 ms 출처 Baekjoon, University of Ulm Local Contest 1997 D 언어 C++ 17 분류 BFS, DFS, 다익스트라 알고리즘 설명 정육면체가 금! 으로 되어있는 상범 빌딩에서 시작지점과 탈출지점이 알려질 때 얼마나 빠르게 상범 빌딩에서 탈출 할 수 있는지 구하는 문제 각 변의 길이가 1인 단위 정육면체의 금! 으로 되어있는 상범빌딩에 갇혔다. 한 번에 움직일 때 1분이 걸린다. 구해야 하는 경우가 가장 빠른 탈출 시간을 요구한다. DFS로 해도 되고 BFS로 해도 된다. 굳이 다익스트라로 구하는 의미가 필요한가 싶긴 하다. 입력을 받을 때 각 문자 사이에 공백이 존재..
BaekJoon 2573 빙산 2019. 2. 3. Link https://www.acmicpc.net/problem/2573 소스결과 2164 KB / 96 ms 출처 Baekjoon, KOI 2006 초등부 2번 언어 C++ 17 분류 BFS, DFS 설명 지구 온난화로 인하여 빙산이 녹아 내릴때 주어진 빙산이 녹아 2개 이상의 빙산으로 분리 될 때 까지 얼마만큼의 시간이 걸리는지 알아내는 문제 먼저, 빙산이 녹는 양은 0이 아닌 현재 위치를 기준으로 상하좌우 4방향의 값이 0인 즉 바닷물인 부분의 수 만큼 녹아 내린다. 또한 같은 시간에 녹아 내리는 양은 탐색 순서에 영향을 받지 않는다. ( (1,1)의 값이 0으로 줄었다고 해서 (1,2)의 값이 3이 줄어드는 것이 아닌 2가 줄어듦) BFS나 DFS가 사용되는 부분은 빙산이 몇개로 이루어져 있는지..
BaekJoon 4179 불! 2019. 2. 1. Link https://www.acmicpc.net/problem/4179 소스결과 3956 KB / 32 ms 출처 Baekjoon, Waterloo's Local Programming Contest 2009 언어 C++ 17 분류 BFS DFS 다익스트라 설명 BOJ 5427 - 불 문제와 유사합니다. 설명 및 알고리즘 - > 링크 https://girlfriend-yerin.tistory.com/70 소스코드 #include #include using namespace std; const int MAX = 1000; const short posX[4] = { 0, 1, 0, -1 }; const short posY[4] = { 1, 0, -1, 0 }; struct Point { short x; s..
Baekjoon 1405 미친 로봇 2019. 1. 21. Link https://www.acmicpc.net/problem/1405 소스 결과 1988 KB / 40 ms 출처 Baekjoon 언어 C++ 17 분류 DFS, 브루트 포스, 탐색 설명 통제할 수 없는 미친 로봇이 n번의 행동 중 로봇의 이동 경로가 단순한 경우의 확률을 구해 내는 문제 앞선 문제의 경우와 다른 점은 확률을 구해야 한다는 점이 가장 눈에 띈다. 이동 경로를 구해야 되는 문제이기 때문에 BFS/DFS를 사용 해야 한다. 하지만 이번 문제는 최단 경로를 구하는 문제가 아니기에 BFS를 사용하는것은 적절하지 않아보인다. 또한 로봇이 이동 할 수 있는 모든 경로에 대해서 탐색 해야한다. DFS를 진행 하면서 브루트 포스가 자동으로 진행 되기 때문에 크게 유의하지는 않아도 된다. 맵의 크기..
BaekJoon 14502 연구소 2019. 1. 18. Link https://www.acmicpc.net/problem/14502 소스결과 1992 KB / 36 ms 출처 Baekjoon 언어 C++ 17 분류 BFS DFS 브루트포스 설명 바이러스가 유출 되었을 때 벽 3개를 이용해서 최대한 많은 안전한 공간을 만들어야 하는 문제이다. BFS와 Brute Force를 동시에 사용 해야 하는 문제 바이러스가 퍼지기 전에 벽을 3개만 더 추가해서 최대한 많은 공간을 확보 해야 한다. 문제를 풀 때 크게 새로 벽을 3개 새우는 단계와 BFS/DFS를 통해 바이러스가 확산하는 경우의 2단계로 나누어야 한다. 따라서 벽을 제외한 안전한공간과 바이러스가 있는 공간을 저장하는 배열 2개가 필요하다. 안전한 공간은 벽을 세우기 위한 용도에 사용되고, 바이러스 공간은 ..

티스토리툴바