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

 

문제 2210번 

 :  5 x 5의 숫자판 존재

   각 칸에는 0~9까지의 숫자가 들어갈 수 있다

 

 :  처음 칸에서 5번 더 이동 가능 (상하좌우로만)

    모두 이동한 칸은 처음 칸을 포함해서 총 6칸  

    중복으로 이동 가능 (즉 갔던 자리 다시 갈 수 있다는 뜻)

 

 :  나올 수 있는 6칸의 숫자를 붙여서 6자리의 경우의 수를 구하여라

 

 

[입력]

 :  다섯 개의 줄에 다섯 개의 정수로 숫자판

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

 

 

[출력]

 :  경우의 수 출력

15

 

 

 [문제접근]

 

• 모든 경로를 하나하나 다 파악해줘야 하기 때문에 DFS 선택!
  
  
• 다른 문제와 달리 방문기록을 표시하는 객체가 없다
  → 해당 문제는 중복을 허용하기 때문이다 
  → 즉, 같은 자리를 다시 찾아갈 수 있다
  
• 다만 경우의 수를 계산하기 위해서는 중복 처리 필요
  → 똑같은 6자리의 숫자는 중복되면 안된다
  → Set 사용
  
  
• 현위치 머무르기 X
  → 본인의 자리를 선택할 수 있다고 생각해서 dx, dy에 (0,0) 좌표도 추가하려고 했지만 오류가 난다
  → 돌고 돌아서 본인의 자리를 스쳐갈 수는 있지만 현자리에서 이동없이 머무르는 것은 안되는 것 같다
  
  
• + 유용하게 쓰기
  → 숫자로 받으면 덧셈 연산이 되지만 애초에 좌표 안에 들어있는 숫자를 String으로 받아서 문자열로 출력
  → 이렇게하면 별다른 로직 없이도 간편하게 6자리의 숫자를 합칠 수 있다
  

 

 

[참고]

JAVA Collection Framework의 상속 기본 구조

https://cocoon1787.tistory.com/527

---

List

- 순서가 있고 중복 허용
- 크기가 가변적

Map

- Key와 Value의 한쌍으로 이루어지는 데이터의 집합
- 순서가 없고 Key값의 중복은 허용, Value값의 중복은 허용X 
- 뛰어난 검색 속도

Set

- 순서가 없고 중복 허용X
- 빠른 검색 속도

 

 

 [코드]

import java.util.*;
import java.io.*;
public class Main{
    static String numMap [][] = new String[5][5]; 
    static int dx[] = {0, 0, 1, -1}; // 상하좌우 이동
    static int dy[] = {1, -1, 0, 0}; // 상하좌우 이동
    static HashSet<String> answer = new HashSet<>();
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        for(int i =0; i<5; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<5; j++){
                numMap[i][j] = st.nextToken();
            }
        }
        
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                dfs(i, j, numMap[i][j], 0);
            }
        }
        System.out.println(answer.size());
    }
    
    public static void dfs(int x, int y, String route, int count){
        if(count == 5){
            answer.add(route);
            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(nowX,nowY,route + numMap[nowX][nowY],count+1);
            }
        }
    }
}

 

 

 [해설]
     

 :  static String numMap [][] = new String[5][5];  2차원 배열의 숫자판
    static int dx[] = {0, 0, 1, -1};  상하좌우 이동 x값
    static int dy[] = {1, -1, 0, 0};  상하좌우 이동 y값
    static HashSet<String> answer = new HashSet<>();  경우의 수를 담을 set 설정
          
 :  for(int i =0; i<5; i++){  5 x 5 배열이므로
            st = new StringTokenizer(br.readLine());  끊어읽기
            for(int j = 0; j<5; j++){  5 x 5 배열이므로
                numMap[i][j] = st.nextToken();  배열판에 값 넣기
            }
    }

 

 :  for(int i=0; i<5; i++){  
            for(int j=0; j<5; j++){  
                dfs(i, j, numMap[i][j], 0);  dfs 실행
            }
    }
        
 :  System.out.println(answer.size());  최종 답 출력
      
 :  public static void dfs(int x, int y, String route, int count){  dfs 실행
        

        if(count == 5){   5번까지 이동하고 마친다
            answer.add(route);   set에 6자리 수의 경로 모두 넣기
            return;
        }
        
        for(int i =0; i<4; i++){  4가지 방향 안에서 이동
            int nowX = x + dx[i];  현재 이동 칸의 x좌표 = 직전 x + 인접 방향
            int nowY = y + dy[i];  현재 이동 칸의 y좌표 = 직전 y + 인접 방향
            if(0 <= nowX && nowX < 5 && 0 <= nowY && nowY < 5){  배열판이 0 ~ 5 사이에 있어야한다
                dfs(nowX,nowY,route + numMap[nowX][nowY],count+1);   dfs 재실행
            }
        }
    }

 

 

이제 풀어보러 갈께요 :)

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

2210번: 숫자판 점프