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

문제

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

2210번: 숫자판 점프

 

풀이 및 소스코드

dfs로 돌리다가 만약 6자리 수가 완성되었다면(cnt == 5) 중복되지 않게 list에 넣어준 후, list의 size를 출력하면 된다.

import java.io.*;
import java.util.*;


class Main {
	static List<String> list = new ArrayList<>();
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int res = 0;
		String[][] map = new String[5][5];

		for(int i=0;i<5;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<5;j++) {
				map[i][j] = st.nextToken();
			}
		}
		for(int i=0;i<5;i++) {
			for(int j=0;j<5;j++) {
				dfs(map, i, j, 0, map[i][j]);
			}
		}
		System.out.println(list.size());
	}
	
	public static void dfs(String[][] m, int x, int y, int cnt, String tmp) {
		if(cnt == 5) {
			if(!list.contains(tmp)) {
				list.add(tmp);
			}
			return;
		}
		for(int i=0;i<4;i++) {
			int nowx = x+dx[i];
			int nowy = y+dy[i];
			if((0<=nowx&&nowx<5)&&(0<=nowy&&nowy<5)) {
				dfs(m, nowx, nowy, cnt+1, tmp+m[nowx][nowy]);
			}
		}
	}
}