백준_2210 숫자판 점프(자바) / DFS + 백 트래킹

시간 & 메모리 제한

문제

입력 & 출력

DFS + 백 트래킹을 이용한 문제풀이

package com.Back;

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

public class Back_2210 {

	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
	static int[][] map;
	static List<String> list = new ArrayList<String>(); 
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		map = new int[5][5];
		
		for (int i = 0; i < 5; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 5; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				dfs(i,j,0,map[i][j]+"");
			}
		}
		System.out.println(list.size());
	}

	private static void dfs(int x, int y, int d,String s) {
		if(d==6) {
			if(!list.contains(s)) { 				
				list.add(s);
			}
			return;
		}
		for (int k = 0; k < 4; k++) {
			int xx = x+dx[k];
			int yy = y+dy[k];
			if(xx<0 || xx>=5 || yy<0 || yy>=5)continue;
			dfs(xx,yy,d+1,s+map[x][y]);
		}
	}
}

- DFS를 이용해서 모든 크기의 위치에 대해서 다 조사를 해줍니다.

 

- map은 int형이기 때문에 +""을 같이 해서 보내면 String 형태로 바꿀 수 있습니다.

 

- 6번의 선택이 끝나면 조건문을 통해서 있는 list이면 추가를 하지 않습니다.

 

- 만약 없는 list이면 추가를 해줍니다.