[백준] 2210. 숫자판 점프 (실버2) - DFS

2210. 숫자판 점프 (실버2)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	10069	7431	5961	74.662%

문제

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

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

입력

다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

출력

첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

예제 입력 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1

예제 출력 1
15

힌트
111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다.

풀이

1. DFS로 내려가면서 문자열 추가, cnt 증가
2. cnt가 6이 됬을 때, hashset에 넣어 중복 제거

import codingTest.Search_2468.Point;
public class Search_2210 {


		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
        N = 5;

		arr = new int[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				DFS(i,j,"",0);
			}
		}
		System.out.println(hash.size());
	}
	public static void DFS(int row, int col, String sb, int cnt) {
		if(cnt==6) { //문자열의 갯수가 6이 되었을 때 
			//System.out.println(sb);
            
            //hashset에 넣어 중복제거
			hash.add(sb);
		}else {
			for(int w=0; w<4; w++) {
            	// 사방을 돌아서 수 찾기
				int xx = row + dx[w];
				int yy = col + dy[w];
				
				if(xx<0 || xx>=N || yy<0 || yy>=N ) continue;
                // 이동한 위치의 x축, 이동한 위치의 y축, 문자열 추가, 문자 갯수 추가
				DFS(xx,yy,sb+arr[xx][yy],cnt+1);
			}
		}
	}
}

* DFS

* 중복을 없애기 위해 Hastset 사용