[백준] code.plus(브루트 포스 Part 1,JAVA)2210번, 숫자판 점프

문제 링크

2210번: 숫자판 점프

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. 숫자판 임의의 위치에서 상하좌우 5번 이동을 진행하여 만들 수 있는 숫자의 개수를 결과로 출력합니다.

2. 만드는 숫자는 0으로 시작해도 상관이 없습니다.

3. 방문했던 위치도 다시 갈 수 있습니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 임의의 위치에서 5번 이동하는 모든 경우를 탐색하여 나올 수 있는 숫자의 개수를 탐색합니다.

 

3. 탐색이 종료한 뒤에 나올 수 있는 숫자의 개수를 결과로 출력합니다.

 

위치 이동

BFS탐색을 이용하여 이동한 횟수가 5번일 때 만들어진 숫자가 중복되었는지 확인합니다.

 

중복일 경우

해당 숫자는 먼저 탐색하였기 때문에 넘어갑니다.

 

중복이 아닐 경우

해당 숫자를 처음 탐색하였기 때문에 저장됩니다.

 

※방문한 위치를 재방문이 가능합니다.

 

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

1	1	1	1	1
1	1	1	1	1
1	1	1	1	1
1	1	1	2	1
1	1	1	1	1

 

2. 임의의 위치에서 5번 이동하는 모든 경우를 탐색하여 나올 수 있는 숫자의 개수를 탐색합니다.

 

111111, 111112....., 212121 = 15가지

 

 

3. 탐색이 종료한 뒤에 나올 수 있는 숫자의 개수를 결과로 출력합니다.

 

나올 수 있는 숫자의 개수 15을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력값을 띄어쓰기 기준으로 나누었습니다.
• 각 위치에서 bfs함수를 실행하여 만들 수 있는 숫자의 모든 경우를 탐색합니다.
• 탐색한 이후 만들 수 있는 숫자의 개수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 BFS탐색으로 이동을 5번 했을 때 만드는 숫자를 탐색합니다.
• inSpace함수는 이동할 위치가 공간에 존재하는지 확인합니다.

 

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

public class Main {
    //위치 관련 정보 클래스
    static class info{
        int x, y, count;
        String value;
        public info(int x, int y, String value, int count) {
            this.x = x;
            this.y = y;
            this.value = value;
            this.count = count;
        }
    }
    static int[][] map = new int[5][5];	//공간 관련 정보 저장 배열
    static int dx[] = {0, 0, -1, 1};		//상하좌우 x변경값
    static int dy[] = {-1, 1, 0, 0};		//상하좌우 y변경값
    static HashSet<String> hash = new HashSet<>();	//숫자 탐색 확인 HashSet
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        //입력값 저장
        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());
        }
        //각 위치에서 BFS탐색으로 만들 수 있는 숫자의 모든 경우의 수 탐색
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++)
                bfs(i, j);
        }
        bw.write(hash.size() + "");	//숫자의 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색으로 5번 이동하여 만들 수 있는 숫자 탐색
    static void bfs(int x, int y){
        Queue<info> q = new LinkedList<>();
        q.add(new info(x, y, String.valueOf(map[y][x]), 1));
        while(!q.isEmpty()){
            info cur = q.poll();
            if(cur.count==6){		//5번 이동 후 숫자 완성시
                if(!hash.contains(cur.value))	//첫 탐색으로 만난 숫자일 경우
                    hash.add(cur.value);
                continue;
            }
            //상하좌우 탐색중...
            for(int i=0;i<4;i++){
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                if(inMap(tempX,tempY))
                    q.add(new info(tempX,tempY, cur.value + map[tempY][tempX], cur.count+1));
            }
        }
    }
    //이동할 위치가 공간에 존재하는지 확인하는 함수
    static boolean inMap(int x, int y){
        if(x>=0 && y>=0 && x<5 && y<5)
            return true;
        return false;
    }
}