[BOJ - JAVA] 2210 - 숫자판 펌프 (백트래킹, DFS)

# 주소

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

2210번: 숫자판 점프

# 문제

# 문제 해설 및 코드 리뷰

import java.util.HashSet;
import java.util.Scanner;

public class Main{
	static int n;
	static int[][] arr;
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1}; 
	static HashSet<String> hashset = new HashSet<>();
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		arr = new int[5][5];
		for(int i = 0; i < 5; i++) {
			for(int j = 0; j < 5; j++) {
				arr[i][j] = scan.nextInt();
			}
		}
		String s = new String();
		for(int i = 0; i < 5; i++) {
			for(int j = 0; j < 5; j++) {
				dfs(i,j,0,s);
			}
		}
		System.out.println(hashset.size());
	}
	public static void dfs(int x, int y, int cnt, String s) {
		if(cnt == 6) {
			hashset.add(s);
			return;
		}
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
				dfs(nx,ny,cnt+1,s+arr[nx][ny]);
			}
		}
	}
}

간단합니다. 

5 x 5 배열에서 6가지 숫자를 상,하,좌,우로 움직여서 만들 수 있는 경우의 수를 묻는 문제입니다.

이 문제를 보자마자 딱 생각이 드셔야 합니다.

바로 '백트래킹'과 'DFS'가 생각 나셔야 합니다. 자료구조는 그 뒤 문제이구요.

백트래킹은 완전 탐색 (브루트포스) 같은 문제 풀이에 탁월합니다.

시간이 많이 걸린다는 단점이 있지만 이것보다 확실하게 모든 경우의 수를 탐색하는 알고리즘은 없으니까요.

즉, 백트래킹은 모든 경우의 수를 탐색하는데 자주 응용됩니다.

그리고 DFS는 깊이 우선 탐색의 약자로서, 인근에 있는 인덱스를 수직 방향으로 탐색하여 연결된 모든 곳의 탐색을 하는데 주로 사용됩니다.

따라서 DFS + 백트래킹의 조합은 DFS의 틀을 따르되 (인접해있다면 수직 방향) 만들 수 있는 모든 조합을 백트래킹 방식으로 조합해서 만들겠단 뜻입니다.

따라서 상,하,좌,우의 방향을 뜻하는 dx와 dy를 모든 DFS, BFS문제 풀 때도 사용하듯이 static으로 정의해주셔야 하고 반드시 백트래킹처럼 index (여기서는 cnt) 가 6이 되었을 때 Hashset에 담아주는 것이 필요합니다.

HashSet 은 중복을 허용하지 않는 자료구조입니다.

따라서 들어오는 값들 중 중복되는 값이 있으면 알아서 걸러지고 쌓이는 값들이 다 다르게 저장되는 것입니다.

어려운 것 한개도 없어요. 질문 있으시면 올려주세요!