"꾸준하게, 지속하자 "

우선 문제를 보자마자 그래프 탐색 알고리즘을 이용하여 "연결요소"의 개수를 파악한 다음 그걸 리스트에 담고, 리스트를 정렬해준 다음, 차례로, 리스트 사이즈출력, 리스트요소들 하나씩 출력 해주면 끝난다. 풀이법을 생각해내는데 5분도 걸리지 않았지만.... 실제 정답을 내는데 디버깅 포함 1시간 걸린거 같다... 내가 실수한 부분은, 이 문제는 "최단거리"나, "백트레킹" 등, 그래프 탐색에 있어서 특수한 조건이 없기 때문에, DFS또는 BFS중 아무거나 사용 가능하다. 이유는 두 기법 모두, 연결된 노드를 전부 방문할수 있고, 그에 맞춰서 카운트 값을 올려줄수 있기 때문이다. 어제 쓴 포스트에서는 BFS를 이용해서 풀었기에, DFS로 풀어볼까 하면서 코드를 짰더니... 계속 리스트 사이즈 1, 값은 48..

우선 순열이란 단어를 보자마자, 아 백트레킹을 이용한 순열을 구하는 것인가? 라는 생각이 들었다. 그러나 문제를 계속 읽으니, 그냥 각 인덱스값, 1부터 N까지에 대응되는 값을 이용하여, 인접리스트나 인접행렬을 통해 노드와 노드사이의 관계를 표현한 다음, 연결요소의 개수를 구하면 된다는 것을 알게 되었다. 처음 난, 이전에 풀어봤던 아파트 단지문제나 배추심기 문제 등에서 좌표평면에 (x,y) 좌표로 노드간의 연결관계를 표현 한 것을, 상화좌우 인접한 좌표로 dfs를 통해 끝까지 탐색하며1을 0으로 바꾸고, 그 곳들을 for문을 통해 처음부터 하나하나씩 dfs로 돌릴때, 해당 좌표가 1이면 카운트 해주는 식으로 풀이를 하면 될줄 알았다. 하지만 이 문제는, 좌표로 나타내었을때, 각 좌표들간의 상관관계가 존..

우선적으로 사용자로부터 N과 M 입력 값을 받는다. 그리고, 연산의 대상이되는 수들을 사용자로부터 N개 입력받는다. N P M을 구해보겠다. 우선 순열이나, 조합 모두 dfs의 방법중 하나인 백트레킹을 이용한다. 1.모든 노드를 탐색해야한다. 2.노드 탐색의 조건이 있다.(한번 방문한 노드는 방문하지 않는다. 그러므로 dfs를 통한 백트레킹 방법을 이용한다. import java.io.*; import java.util.*; public class Main { static int[] arr; static int[] output; static boolean[] value; static int N; static int M; public static void main(String[] args) throws I..