백준 2210

●문제 출처

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

●정리(요약)
5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

●코드

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

public class Main {
	static boolean [] visited = new boolean[1000000];
	static int count;
	static int [] dx = {1,-1,0,0};
	static int [] dy = {0,0,-1,1};
	static int [][] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		arr = new int[5][5];
		for(int i = 0; i<5; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j<5; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		count = 0;
		for(int i = 0; i<5; i++) {
			for(int j =0; j<5; j++) {
				dfs(i,j,arr[i][j],1);
			}
		}
		
		System.out.println(count);
	}
	
	public static void dfs(int x, int y,int str, int cnt) {
		if(cnt==6) {
			if(!visited[str]) {
				visited[str]= true;
				count++;
			}
			return;
		}
		
		
		for(int i = 0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx>=0 && ny>=0 && nx<5 && ny<5) {
				int nxtNum = str * 10 + arr[nx][ny];
				dfs(nx,ny,nxtNum,cnt+1);
			}
		}
	}
}

●느낀 점