[백준] 2210번 : 숫자판 점프(JAVA)

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

2210번: 숫자판 점프

풀이

5 x 5크기의 배열로 값을 입력받습니다.

5 x 5 크기만큼 dfs를 실행합니다. (위치x, 위치y, 카운트, 위치 값)

입력받은 위치의 상하좌우가 가능하면 dfs로 위치를 변경후 실행시킵니다. (아닐경우 continue)

count가 5인경우 5개의 경로를 지나온것이므로 HashSet에 값을 저장합니다.(중복 제거)

 

모든 dfs를 지난 후 set의 크기를 출력해주면 됩니다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	static boolean[][] visited = new boolean[5][5];
	static int[][] num = new int[5][5];
	static int[] dy={1, -1, 0, 0}, dx = {0, 0, 1, -1};
	static HashSet<Integer> set = new HashSet<>();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for(int i = 0; i < 5; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < 5; j++) {
				num[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i = 0; i < 5; i++) {
			for(int j = 0; j < 5; j++) {
				dfs(i, j, 0, num[i][j]);
			}
		}
		
		System.out.print(set.size());
	}
	
	public static void dfs(int index, int depth, int count, int sum) {
		if(count == 5) {
			set.add(sum);
			return;
		}
		
		for(int i = 0; i < 4; i++) {
			int x = index + dx[i], y = depth + dy[i];
			
			if(x < 0 || x > 4 || y < 0 || y > 4) {
				continue;
			}
			
			dfs(x, y, count + 1, sum * 10 + num[x][y]);
		}
	}
}