[백준] 2210번 숫자판 점프 (자바 풀이)

문제

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

2210번: 숫자판 점프

 

풀이

이 문제는 간단한 BFS 문제이다. 다만 일반적인 BFS와 달리 방문 여부를 체크하지 않는다. 대신 6개의 숫자를 택하면 더 이상 탐색을 진행하면 안 되는 식으로 구현하면 된다.

 

나는 다음과 같은 Node 클래스를 만들어서 큐의 원소로 사용했다.

 

public static class Node{
		int x;
		int y;
		String str;
		Node(int x,int y, String str){
			this.x = x;
			this.y = y;
			this.str = str;
		}
	}

 

이후 모든 원소에서 BFS 탐색을 진행하면서 6자리의 숫자를 선택하면 HashSet<String>에 String 형식으로 넣었다.

즉, HashSet을 이용하여 중복되는 원소를 피하는 방식을 택했다.

 

이후 HashSet의 size를 출력하면 정답이다.

 

코드

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

public class Baekjoon_2210 {
	static HashSet<String> ans = new HashSet<>();
	static int arr[][] = new int[5][5];
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		for(int i=0; i<5; i++) {
			for(int j=0; j<5; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		
		for(int i=0;i<5; i++) {
			for(int j=0; j<5 ; j++) {
				bfs(i,j);
			}
		}
		
		System.out.println(ans.size());
				
	}
	
	public static void bfs(int x, int y) {
		Queue<Node> q = new LinkedList<>();
		
		q.add(new Node(x,y,""));
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			if(cur.str.length() >= 6 ) {
				ans.add(cur.str);
				continue;
			}
			
			for(int i=0; i<4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				if(nx<0 || ny <0 || nx>=5 || ny>=5) continue;
				
				q.add(new Node(nx,ny, cur.str+String.valueOf(arr[nx][ny])));
			}
		}
	}
	
	public static class Node{
		int x;	// x좌표
		int y;	// y좌표
		String str;	// 선택한 숫자
		Node(int x,int y, String str){
			this.x = x;
			this.y = y;
			this.str = str;
		}
	}

}