[백준] 2210 숫자판 점프 - DFS(깊이우선탐색) + BFS(너비우선탐색) + 완전탐색(BruteForce) JAVA

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

2210번: 숫자판 점프

코드설명

DFS 를 활용하거나 BFS를 활용하여 풀 수 있습니다.

 

저는 이번문제는 DFS를 활용했습니다.

BFS를 활용할것이라면, 각 4방향으로 큐를 계속 더해주면서 연산횟수를 가지고 다니면서 5가 넘어가면 해당 큐를 hashset에 넣어주면 됩니다. 이떄 처음에 큐를 사용하기에 어떻게 해야하나 고민했었는데 큐의 횟수가 5 넘어가면 종료시켜주면 DFS와 다를것이없습니다.

 

이떄, 수의 길이를 String 형태로 처리할수도 있으나 아래와 같이 (num*10) + map[nr][nc]로 처리하여 문자열 처리 대신 정수로 처리합니다.

DFS(level + 1, nr, nc, (num*10) + map[nr][nc]);

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	
	public static int N;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int answer;
	public static int[][] map;
	public static HashSet<Integer> hashset = new HashSet<>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	map = new int[5][5];
    	for(int i=0;i<5;i++) {
    		StringTokenizer 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(0, i, j, map[i][j]);
    		}
    	}
    	System.out.println(hashset.size());
    	
    	
    }
	public static void DFS(int level, int startR, int startC, int num) {
		if(level == 5) {
			hashset.add(num);
			return ;
		}
		for(int dir=0;dir<4;dir++) {
			int nr = startR + dx[dir];
			int nc = startC + dy[dir];
			if(nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue;
			DFS(level + 1, nr, nc, (num*10) + map[nr][nc]);	
		}
		
		
		
	}
}

 

코드 2 입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, H, W, K;
	public static int answer = 0;
	public static int[][] matrix;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0, 0, -1, 1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());

		N = 5;
		matrix = new int[N][N];
		for(int i=0;i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());	
			for(int j=0;j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		HashSet<String> hashset = new HashSet<>();
		for(int i=0; i<N; i++) {
			for(int j=0;j<N; j++) {
				DFS(0, i, j, new String(), hashset);
			}
		}
		System.out.println(hashset.size());
	}
	
	public static void DFS(int depth, int r, int c, String str, HashSet<String> hashset) {
		if(depth == 6) {
			hashset.add(str);
			return ;
		}
		
		for(int dir = 0; dir < 4; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			if(nr < 0 || nr >= N || nc < 0 || nc >= N) {
				continue;
			}
			DFS(depth + 1, nr, nc, str + matrix[r][c], hashset);
		}
		return ;
	}
	

}