문제 url:
N과 M(1)
문제:
🤔 문제 알아보기
백트래킹 카테고리의 첫 번째 문제이다. 백트래킹에 대해서는 나중에 자세하게 알아보는 것으로 하고
오늘은 간략하게 백트래킹에 대해서 알아본 바를 설명하고자 한다.
백트래킹이란?
해를 찾는 도중 해가 아니면, 다시 되돌아가서 해를 찾는 기법으로
즉, 모든 경우의 수를 전부 고려하는 알고리즘이다. 또한, 상태공간을 트리로 나타날 수 있을때 적합한 방식이라고 한다.방식에 따라서 깊이 우선탐색(DFS)과 너비 우선탐색(BFS), 최선 우선 탐색이 존재,
만약 모든 경우의 수를 고려해야 하는 문제라면 DFS가 낫다고 한다.
여기까지 간략하게 백트래킹이 무엇인지 알아봤고, 이제 문제를 알아보자,
먼저, M과 N을 입력받는데, N은 1부터 N까지의 자연수를 의미하며 M은 1부터 N까지 중복 없이 M개를 고른 수열이라고 한다.
즉, 1부터 N까지의 숫자를 출력할 것인데, 한번에 총 M개만큼 출력을 할 것이다. 그러나, 중복되는 값이 존재해서는 안된다.
이 말은 1,1 혹은 이전에 1,2를 출력했다면 1,2를 출력하지 못해야 한다는 것이다.
이제 문제 조건을 알아봤으니, 구현을 어떻게 할 것인가를 생각해보자
먼저 중복이 되면 안되는 조건이 존재한다. 그렇다면! 현재 방문중인 숫자는 접근을 하지 못해야 한다.
현재 1에 머물고 있는데, 만약 1에 접근하려고 하면 안된다는 것이다.
그렇게 하기 위해서는 현재 머물고 있는 수를 보관할 수 있는 배열이 필요할 것이다.
우리는 이를 visited배열을 활용해 구현하고자 한다.
visited 배열은 현재 해당 숫자에 머물고 있다면 true, 그렇지 않으면 false를 주어 중복된 숫자는 접근하지 못하게 하는 것이다
또한 tc에서 4,4를 입력했을 때 출력을 보면 1,2,3,4 / 1,2,4,3 ... 인 것을 볼 수 있는데, 여기서 힌트를 조금 얻자면 1,2까지는 공통적으로 들어가는 것을 볼 수 있다.
그럼 현재 깊이를 활용해 깊이 2까지 구현 된 것을 볼 수 있는데, 여기서 깊이 3에 대해서 다르게 구현을 하면 된다.
해당 부분은 코드와 함께 알아보면 이해가 쉬울 것이다.
🐱👤 실제 코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int[] arr;
static boolean[] visited;
static StringBuilder sbd;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sbd = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
arr = new int[M];
visited = new boolean[N];
backtracking(N, M, 0);
System.out.println(sbd);
}
static void backtracking(int N, int M, int depth) {
if(depth == M) {
for(int i = 0; i < M; i++) {
sbd.append(arr[i]).append(" ");
}
sbd.append("\n");
return;
}
for(int i = 0; i < N; i++) {
if(!visited[i]) {
visited[i] = true;
arr[depth] = i + 1;
backtracking(N, M, depth + 1);
visited[i] = false;
}
}
}
}
😎 코드 풀이 및 해석
위에서 설명했듯, 중복값이 들어오는 것을 막기 위해 현재 머물고 있는 숫자를 체크할 visited 배열과 출력을 위한 arr 배열을 선언하였다.
또한, backtracking 메서드는, dfs구조로 깊이에 따라서 값을 달리 주기 위해 depth라는 파라미터를 받는다.
이제 코드를 살펴보도록 하자
1번 째 코드
if(depth == M) {
for(int i = 0; i < M; i++) {
sbd.append(arr[i]).append(" ");
}
sbd.append("\n");
return;
}아까 출력을 위해 arr 배열을 선언했다고 했는데, 말 그대로 현재 depth가 M과 같으면 현재 배열을 출력하는 로직이다.
이를 조금 더 설명하면, depth는 깊이라고 했다. 만약 tc로 4, 2를 입력받았다고 가정하면,
1, 2 / 1, 3 / 1, 4 .. 이런식으로 출력이 될 것이다.
즉, 만약 depth와 M이 같으면 현재 값을 출력하면 된다. 또한 return을 통해 재귀를 빠져나갈 수 있다.
2번 째 코드
for(int i = 0; i < N; i++) {
if(!visited[i]) {
visited[i] = true;
arr[depth] = i + 1;
backtracking(N, M, depth + 1);
visited[i] = false;
}
}필자도 여기서 많이 헷갈렸다. 해당 코드는 직접 노트에 그려보는 것이 가장 확실하지만!
시간이 없는분을 위해 같이 한번 살펴보자
필자는 TC 4,4가 주어졌을 때를 가정해서 설명하겠다.먼저 초기 visited 배열은 전부 false이다. 그래서
!visited[0]은 true로 조건을 충족하기 때문에 다음 로직을 따른다.
그런 다음 현재 숫자에 머물고 있기 때문에 true로 초기화 해 해당 숫자에 접근하지 못하도록 하며
depth(현재 0번째)에 1를 삽입한다.
| depth | arr |
|---|---|
| 0 | 1 |
backtracking메서드를 재귀호출한다.(4,2,1)
여기서 중요한 것이 있다. arr 배열에는 i +1만큼, backtracking 메서드에는 depth +1을 입력하는데,
만약 여기서 i++ 혹은 depth++를 하면 사고난다...그 이유는 만약 해가 아닐 경우 다시 돌아왔을 때, 이전에 존재하는 i와 depth를 그대로 사용해야 하는데, 만약 i++, depth++를 해버리면, 값이 영구적으로 변경되기 때문에 찾을 수 없게 되기에
반드시 주의해야 한다.
현재 depth는 1로 m(4)과 다르기 때문에 다시 반복문 로직으로 이동한다.
i가 0일때는 현재 true이기 때문에 조건문을 동작하지 않고, 바로 i = 1로 넘어가고
현재 i = 1일때는 방문한적이 없기 떄문에 조건문을 동작하여 현재 값은 다음과 같다.
| depth | arr |
|---|---|
| 0 | 1 |
| 1 | 2 |
그런 다음, 다시 재귀호출을 진행한다. 이때는 (4,2,2)가 입력된다.
i가 0,1일 때는 현재 방문중이기 때문에 넘어가고 2일 경우는 방문하지 않았기 때문에 동작
| depth | arr |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 3 |
다시 재귀호출 이때는 (4,2,3)가 입력된다.
i가 0, 1, 2일 때는 방문중이니 넘어가고 마지막 3인 경우를 동작
| depth | arr |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 3 |
| 3 | 4 |
그런 다음 (4,2,4)가 입력되며 현재 depth는 m(4)와 같이 때문에 1,2,3,4가 출력된다.
이제부터는 조금 중요하기 때문에 위는 대충 봐도 괜찮지만 아래줄은 조금 주의깊게 보기 바란다.
코드가 위에 있어서 스크롤 올리지 말라구 다시 가져왔다.
for(int i = 0; i < N; i++) {
if(!visited[i]) {
visited[i] = true;
arr[depth] = i + 1;
backtracking(N, M, depth + 1);
visited[i] = false;
}
}자!! 현재 depth 4를 준 재귀호출이 출력과 함께 return되어 무사히 끝났다. 그런 다음 visited[3]은 이제 방문이 종료되었기 때문에 false로 변경해준다.
우리는 이제 기억해야 하는 것이 있다. 현재 시점은 depth가 3인 시점이고 해당 재귀호출이 종료되었다. 이제 되돌아 가면 다음 depth는 어떻게 되는 것인가??
| depth | arr |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 3 |
우리는 현재 depth가 2인 시점으로 돌아왔고, 현재 visited[2]는 false로 변경해준다.(3에 해당하는 값)
그런 다음 현재 i는 2이기 때문에 반복문은 i가 3이 될 때까지 반복해야 한다.
즉, 현재 depth가 2인 시점에서 반복문이 돌아 현재 i가 3인 시점이다.
또한 visited[3]은 false이기 때문에 해당 조건문을 동작할 것이다. 그러면 arr[depth = 2]에는 3 + 1인 4가 들어 갈 것이고, 테이블로 보면 다음과 같다.
| depth | arr | i |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 2 | 1 |
| 2 | 4 | 3 |
그 다음, i가 3인 시점에서 다시 재귀호출을 진행할 것이다. (4,2,3)이 입력된다.
그러면 depth가 3인 시점에서 i는 0과 1은 현재 방문중이기 때문에 넘어가고 i가 2인 경우는 현재 visited[2]가 true이기 때문에 arr[3]에는 3값이 입력될 수 있는 것이다. 그 후, 다시 재귀호출과 함께 depth가 4가 되어 출력과 return으로 마무리 된다.
그럼 다시 테이블을 그려 보면 다음과 같아질 수 있는 것이다.
| depth | arr |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 3 |
이를 계속해서 반복하면 우리가 원하는 형태를 볼 수 있을 것이다.
✨ 회고
가면 갈수록 문제 난이도가 높아지고, 공부해야 할 것이 많아진다. 그만큼 필자 수준 역시 높아졌다고 생각하니 뿌듯하지만 반대로 이제부터 시작이라는 점에서 사실 때려치고 싶은 생각이 굴뚝같기도 하다
천 리 길도 한 걸음부터라고 알고리즘을 공부하고자 마음 먹은 이상 매일 꾸준히 1일 1포스팅을 지키며,
공부해 나가고 나면 어느덧 코테도 합격할 수 있는 선에 와있지 않을까 생각한다.
알고리즘 공부를 하면서 까먹었던 수학 지식들 그리고 몰랐던 자료구조들도 알아가고
더욱이 java로 준비하면서, 자바에 대해서 알아가는 모습에서 확실히 2달전의 필자보다 성장한 모습이 보인다.
그러니.. 해당 포스트를 보는분이 계신다면 같이 열심히 해보자
❤ 참고자료
