DFS

[백준] 9663 - N-Queen (자바/Java)

문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. dfs를 활용해서 풀 수 있다는 건 쉽게 파악이 되는데 시간 초과와 메모리 초과때문에 오래 걸린 문제였다. 일단 처음에는 chess 배열에 queen을 하나씩 저장하면서 dfs로 깊이가 N이 될 때까지 검사하려고 하였다. r과 c를 이중 for문을 돌며 모두 검사하다 보니 row=0일 때 검사한 결과를 다시 row=1일 때도 추가하는 문제가 발생하였다. 그래서 dfs 함수에 row를 변수로 넣어주..

[SWEA] 2819 - 격자판의 숫자 이어 붙이기

배열의 모든 원소에 대해 사방탐색을 6번 진행하는 것이다. dfs를 통해 구현하면 되는데, 한 번 방문한 원소도 다시 방문할 수 있으니 방문여부를 검사할 필요는 없다. 결과값의 중복을 제거하기 위해 hashSet을 사용하였다. 7개의 결과값을 담을 ans배열을 static으로 선언하여 depth가 1 증가할 때마다 ans[depth]에 수를 담았다. 모든 원소에 대해 dfs를 수행하고, ans배열의 0번 index에 초기값을 담아 진행한다. for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) { ans[0] = arr[i][j]; dfs(arr, i, j, 1); } dfs는 사방탐색으로 한다. 먼저 깊이가 7이 되면 결과값을 return한다. 그 다음 사..

[백준] 11725 - 트리의 부모 찾기 (자바/Java)

문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 방법 자체는 dfs를 이용하면 돼서 어렵지 않은데, 메모리와 시간 초과 때문에 오래 걸렸다. 1을 루트로 하기 때문에 1을 시작으로 해서 dfs를 진행하고, 부모 노드를 찾아야 해서 HashMap에 각 child의 부모 노드를 value로 하여 값을 추가하였다. 처음에는 dfs를 각 노드를 찾을 때마다 반복해서 시간이 오래 걸렸는데, dfs는..

[백준] 15650 - N과 M (2) (자바/Java) 백트래킹 DFS 조합

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 이전 문제와 달라진 점은 전의 문제가 순열이었다면 이번에는 조합을 구하는 경우이다. 조건에 수열이 오름차순이라는 것이 추가되었는데, 이는 즉 1 2 3 4만 허용되고, 1 2 4 3, 1 4 3 2 등은 허용되지 않는 것이니 중복을..

[백준] 15649 - N과 M (1) (자바/Java) 백트래킹 DFS

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 이 문제는 백트래킹을 활용한 문제이다. 그 중에서도 DFS를 활용하여 문제를 풀었다. 먼저 방문 여부를 체크할 check 배열을 만들고, 결과를 담을 result 배열을 만들었다. cnt가 0부터 시작해서 M이 될 때까지 dfs를 계속하는데, 방문되지 않은 노드를 ..