[Algorithm][JAVA] 백준 11651번: 좌표 정렬하기 2

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

---

문제

자연수 N과 M이 주어질 때,

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구해라. (수열의 길이는 M)

 

ex. 3 1을 입력하면 1 2 3 출력

 

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.

중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

문제 접근

문제를 보고 대체 뭘 어떻게 해야 되는지 전혀 감이 안 잡혀서 결국 구글링을 했다.

구글링을 하고 난 뒤, 이 문제는 대표적인 백트래킹 문제라는 것을 알게 되었다.

 

그리고 내가 한 생각은......

그... 백트래킹이 그래서 뭔데? 

... 그렇게 됐다.

 

백트래킹과 DFS 개념 참고 링크:

https://chanhuiseok.github.io/posts/algo-23/

[백준] 15649번 : N과 M (1) - JAVA [자바] (tistory.com)

 

백트래킹

- 노드의 유망성을 판단한 뒤, 유망하지 않은 노드라면 다른 노드를 찾는 방법

유망하다: 해가 될 가능성이 있다

유망하지 않은 노드에 가지 않는 것: 가지치기

가지치기를 잘한다 -> 백트래킹의 효율성 증가

- 쉽게 말해 해를 찾기 위해 모든 경우의 수를 탐색하며 만약 막히면 되돌아가서 다시 경우의 수를 탐색하는 방법

- 특정한 조건을 만족하는 경우의 수만 살펴보는 것

 

DFS (깊이 우선 탐색)

- 하나의 순회 알고리즘으로 탐색 알고리즘, 가능한 모든 경로(경우의 수, 후보)를 탐색

- 어떤 노드를 방문 (방문 노드는 방문했다고 표시)하고 그 다음 그 노드와 인접한 노드를 방문, 이 과정을 방문이 안 된 노드가 없을 때까지 반복하는 게 바로 DFS!

- 백트래킹의 방법 중 하나

 

이 문제는 백트래킹을 DFS를 통해 구현하는 문제이다!

 

코드

import java.util.Scanner;

public class _15649 {

	static int N, M; //입력 받을 N과 M 변수 선언
	static int list[]; //숫자의 방문 여부를 체크할 배열 선언
	static int check[]; //방문 여부 결과를 저장할 배열을 선언
	
	/* DFS 메서드 - 반복 횟수를 인자로 받음, 결과 저장 배열에 0번 인덱스부터 저장하기 위해 초기 0부터 시작 */
	static void dfs(int cnt) { 
			
		if(cnt == M) { //0부터 M번까지 반복했으면 하나의 처리가 완성
			for(int i = 0; i < M; i++) { 
				System.out.print(list[i]+" "); //현재 결과 저장 배열을 출력
			}
			System.out.println(""); //각 수열은 공백으로 구분해서 출력해야 된다는 조건이 있음
			return; //DFS 종료 
		}
		
		for(int i = 1; i <= N; i++) { //1부터 N까지의 자연수
			if(check[i] == 1) continue; //이미 방문한 배열이면 건너뛰기
			check[i] = 1; //방문하지 않았다면, 방문처리
			list[cnt] = i; //현재 반복 횟수에 해당하는 배열(방문 여부 체크 배열)에 i값 넣기
			dfs(cnt + 1); //반복 횟수를 증가시키기
			check[i] = 0; //DFS가 종료 후엔 방문 여부 0으로 초기화
		}
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);	
		
		N = in.nextInt(); //N 입력 받기
		M = in.nextInt(); //M 입력 받기
		
		check = new int[9]; //N과 M의 최대범위 
		list = new int [9];
		dfs(0);
	}
}

 

코드 링크: [백준,BOJ 15649] N과 M(1) (JAVA 구현) — 코오오딩 (tistory.com)

 

백트래킹과 DFS 개념을 공부했으나, 여전히 코드를 짜는 것은 어려워서 결국 코드도 구글링했다.

C언어로 풀까 하다가 시험 공부도 할 겸 JAVA로 문제 푸는 방법을 알아봤다.

코드 한 줄마다 해석해 보는 방식으로 공부했으나... 아직도 어렵다는 느낌은 사라지지 않았다.

이 문제를 기회로 백트래킹과 DFS에 대해 공부할 수 있어서 좋았고,

스스로 코드에 사용하기 위해선 많은 공부와 노력이 필요할 것 같다.

 

아좌좌!

 

실행 화면

 

결과

백준 문제를 자바로 풀 때에 클래스 이름을 Main으로 설정해야 한다! 안 그러면 컴파일 에러가 난다.