DFS (14) 썸네일형 리스트형 [백준] 17406번: 배열 돌리기 4 (JAVA 풀이) 문제 https://www.acmicpc.net/problem/17406풀이이 문제를 풀어나간 순서를 간단히 말하자면 다음과 같다.1. 연산 순서 정하기2. 회전 연산하기3. 배열값 구하기 1. 연산 순서 정하기회전 연산이 여러개면, 연산을 수행한 순서에 따라 배열이 달라지기 때문에 연산 순서 조합을 모두 구해야한다.연산은 최대 6개이기때문에 배열을 미리 만들어놔서 입력받을때 배열에 차례로 저장해두었다.배열에 연산을 미리 저장해둔 이유는 배열의 인덱스를 이용하여 연산 순서 조합을 구하기 위함이다!연산순서는 dfs(백트래킹) 방법으로 구했다. 2. 회전 연산하기제일 많은 시간이 걸렸던 부분.. [SWEA] 1954번: 달팽이 숫자 문제를 연습한다면 좋을 것 같다..일단, 1번에서 정한 연산 순서에 따라 .. [백준] 17141번: 연구소2 (C++ 풀이) 문제 https://www.acmicpc.net/problem/17141풀이1.입력으로 주어진 바이러스를 놓을 특정위치 중에 내가 놓을곳 m개를 골라야 한다.나는 입력을 받으면서 따로 pair place[10]배열에 바이러스를 놓을 좌표를 저장해두었다.DFS로 place배열의 인덱스를 가지고 그 중에 m개의 장소를 골랐다. 2.m개의 장소를 고르고 나면 그 부분을 출발점으로 두어야한다.vis[x][y]는 0으로 두고 큐에 넣는다. (vis배열은 -1로 초기화되어있고, 퍼져나가는 시간을 저장해둘것이다.)m개의 장소에 대해 큐에 모두 넣고 BFS를 시작한다. 3.BFS는 아직 방문하지 않았고(vis == -1), 맵이 0이거나 2인 부분을 방문한다. 4.BFS로 vis배열을 모두 채우고, 이중for문으로 v.. [백준] 9205번: 맥주 마시면서 걸어가기 (C++ 풀이) 문제 https://www.acmicpc.net/problem/9205풀이점과 점사이의 맨해튼 거리를 계산하고그 거리가 20병*50m=1000m 이내이면 그래프로 저장한다.dfs로 시작점인 0부터 탐색을 하는데첫번째 예제에서는 모든 좌표가 1000이내에 있어서 그래프가 하나로 연결되어있다.그래서 시작점에서 도착점까지 무사히 갈 수 있는데두번째 예제에서는 중간에 1000이내에 갈 수 없는 지점이 있다.그래서 그래프가 2개가 되는데 시작점에서부터 dfs탐색을 할 경우 도착점까지 탐색을 하지 못하게 된다.dfs탐색을 마친후 도착점에 방문했는지 여부에 따라 happy or sad를 출력하면 된다. 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/9.. [백준] 17135번: 캐슬 디펜스 (C++ 풀이) 문제 https://www.acmicpc.net/problem/17135풀이궁수배치를 어떻게 하느냐에 따라 죽일 수 있는 적의 수가 다르다. 최대한 많은 수의 적을 죽일때 그 수를 출력하는 문제이다.1. 나는 dfs로 궁수를 배치했다. 최대 15C3의 조합으로 궁수를 배치할 수 있다.2. 3명의 궁수를 배치하고 나면 각 궁수에 대하여 죽일 수 있는 적을 표시하는 작업을 한다.나는 이 작업을 bfs로 탐색했다.3. bfs로 해당 궁수에 대하여 사정거리까지 퍼져나가면서 가장 가깝고 제일 왼쪽에 있는 적을 찾는다.bool형 2차원배열에 찾은 적을 true로 표시한다. 궁수 3명이 한명의 적을 선택해도 상관없다. 각각이 찾으면 true로 표시할 뿐이다. 궁수 3명을 다 돌고 나면 true로 표시한 적을 1에서 .. [백준] 17069번: 파이프 옮기기2 (C++ 풀이) 문제 https://www.acmicpc.net/problem/17069풀이블로그 풀이를 보았다...파이프 옮기기1과 같은 문제인데 범위만 다른 문제이다파이프 옮기기1은 N이 16까지라면 이것은 32까지다. 같은 코드를 제출했더니 메모리초과가 떴다.DFS+DP 방법으로 풀었다.dp는 3차원 long long 배열이다. 예제를 보면 출력 답이 int 범위를 넘는 것을 알 수 있다.dp[a][b][c] = d의 의미 : (a, b)에서 c방향으로의 탐색을 했는데 (n-1, n-1)까지 갈 수 있는 경우의 수가 d이다.dp값을 -1로 초기화해놓는다. 그 이유는 -1이 아직 방문하지 않음을 뜻하고0은 목적지에 갈 수 있는 경우가 없다는 뜻!목적지에 도착하면 1을 리턴한다! 그러면 재귀가 순서대로 빠지면서 경로에.. [백준] 11403번: 경로 찾기 (C++ 풀이) 문제풀이dfs탐색을 통해 풀었다.한 행씩 탐색하면서 갈 수 있는 길마다 체크하고, 체크되어있는곳만 1을 출력하는 방법으로 프린트했다.가는 길이 있고 아직 가지 않은 정점이면 방문하고 dfs 타고 들어가는 방식으로 구현했다.코드결과 [백준] 14888번: 연산자 끼워넣기 (C++ 풀이) 문제풀이연산자의 순서를 dfs를 통해 정하면 된다.수식이 만들어지면 for문을 통해 앞에서 차례대로 계산하면 된다.최소값의 초기값을 10억+1로 하고, 최대값의 초기값은 -(10억+1)로 했다.코드결과 [백준] 1759번: 암호 만들기 (C++ 풀이) 문제https://www.acmicpc.net/problem/1759 풀이dfs탐색을 통해 구현했고 N과 M 시리즈의 응용버전이라고 할 수 있겠다.대신, 암호에 최소 1개의 모음과 2개의 자음을 포함한다는 조건을 처리해야한다. 코드https://www.acmicpc.net/source/12191961 결과 이전 1 2 다음
