[SWEA] 2819. 격자판의 숫자 이어 붙이기

문제

4×4 크기의 격자판이 있다. 격자판의 각 격자칸에는 0부터 9 사이의 숫자가 적혀 있다.

격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 된다.

이동을 할 때에는 한 번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 0102001과 같은 수를 만들 수도 있다.

단, 격자판을 벗어나는 이동은 가능하지 않다고 가정한다.

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

 

풀이방법

DFS(깊이 우선 탐색)알고리즘으로 문제를 해결

 

방문했던 노드를 재방문할 수 있는 길이가 7인 모든 경로를 구한다.

 

이 때 중복되는 숫자를 처리하는 방법은 0부터 9999999까지 인덱스를 가지는 배열을 만들고

 

7자리 숫자를 찾을 때마다 이에 해당하는 인덱스에 값을 1로 표시한다.

 

최종적으로 배열의 원소 값 1의 개수가 격자판에서 만들 수 있는 경로의 개수가 된다.

 

소스코드

package samsung;

import java.util.*;

public class s_2819 {
	static String[][] a;
	static int cnt;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int[] visit;
	public static void dfs(int x, int y, int depth, String s) {
		if(depth == 6) {
			s+= a[x][y];
			int num = Integer.parseInt(s);
			if(visit[num] == 0) {
				visit[num] = 1;
				cnt++;
			}
			return;
		}
		
		s += a[x][y];
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx >= 0 && ny >= 0 && nx < 4 && ny < 4) {
				dfs(nx, ny, depth+1, s);
			}
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			cnt = 0;
			a = new String[4][4];
			visit = new int[10000000];
			for(int i = 0; i < 4; i++) {
				for(int j = 0; j < 4; j++) {
					a[i][j] = String.valueOf(sc.nextInt());
				}
			}
			for(int i = 0; i < 4; i++) {
				for(int j = 0; j < 4; j++) {
					String s = "";
					dfs(i, j, 0, s);
				}
			}
			
			System.out.println("#" + t + " " + cnt);
		}
	}
}