백준 2210번 : 숫자판 점프

www.acmicpc.net/problem/2210

2210번: 숫자판 점프

2210 숫자판 점프

 

 구현 방법

 가능한 모든 곳을 탐색해야 하기 때문에 브루트포스 알고리즘을 사용해주었습니다.

깊이를 따라 가야하기 때문에 dfs를 통해 탐색을 진행하였습니다.

한 번 거쳤던 칸은 다시 거쳐도 되므로 방문체크는 따로 하지않고 카운팅을 해주어 다섯 곳을 이동했으면 중복을 허용하지 않는 TreeSet을 구현하여 해당 문자를 삽입해주었습니다. 

다섯번을 이동했으면 더 이상의 탐색을 끝내고 return 후 다음 방향을 탐색해줍니다. 

마지막으로 삽입했던 숫자가 빠져야하지 때문에 substring을 이용하여 문자열을 잘라주었습니다.

 

 구현 코드

package BOJ.Silver;

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

public class BOJ2210_숫자판점프 {
	static String num;
	static int[][] map, deltas= {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static TreeSet<String> ans;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		map = new int[5][5];
		for (int r=0;r<5;r++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int c=0;c<5;c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		ans = new TreeSet<>();
		// 입력완료
		num = null;
		for (int r=0;r<5;r++) {
			for (int c=0;c<5;c++) {
				num = map[r][c]+"";
				dfs(r, c, 0);
			}
		}
		System.out.println(ans.size());
	}
	
	static void dfs(int r, int c, int cnt) {
		if (cnt == 5) {
			ans.add(num); // 5곳을 탐색하였다면 tree에 추가
			return;
		}
		for (int d=0;d<4;d++) {
			int nr = r+deltas[d][0];
			int nc = c+deltas[d][1];
			if (isIn(nr, nc)) {
				num+=map[nr][nc]; // 해당 숫자 저장
				dfs(nr, nc, cnt+1);
				num = num.substring(0, num.length()-1); // 마지막 값 빼주기
			}
		}
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<5 && nc>=0 && nc<5;
	}
}

 

정답!