[Silver II/JAVA] 2210 숫자판 점프

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

 

 

조건

• 숫자판의 크기는 5*5
• 인접한 네 방향으로 다섯번 이동 (위, 아래, 오른쪽, 왼쪽)
• 한 번 거쳤던 칸을 다시 거쳐도 됨 = 방문 체크 필요없음
• 서로 다른 여섯 자리 수들의 개수 구하기

필요한 것

• 숫자판(grid) 2차원 배열
• 방향 이동을 위한 배열 dx, dy
• 중복을 제거할 수 있는 Set

풀이

• grid 2차원 배열에 값 입력받기
• 각각의 정점(숫자판의 숫자)에서 DFS 탐색하기
• 인접한 네 방향으로 이동

int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};

/*
아래 : dx=1 dy=0 -> 행 번호 1증가 x+1
위 : dx=-1 dy=0 -> 행 번호 1감소 x-1
오른쪽 : dx=0 dy=1 -> 열 번호 1증가 y+1
왼쪽 : dx=0 dy=-1 -> 열 번호 1감소 y-1
*/

• grid 내에 존재하는지 체크하면서 DFS 탐색, 문자열의 길이가 6이 되면 탐색 종료하고 set에 결과 저장
• Set 자료구조 : 중복된 값 허용하지 않음, 순서 없음

Set<String> set = new HashSet<>();
set.add("A");
set.add("B");
set.add("A");
System.out.println(set); //출력 : [A,B] (순서x)

• set의 사이즈를 출력하면 결과가 된다.

전체 코드

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

public class Main{
    static int[][] grid = new int[5][5];
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static Set<String> set = new HashSet<>();
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        //grid 초기화
        for(int i=0; i<5; i++){
            String[] str = br.readLine().split(" ");
            for(int j=0; j<5; j++){
                grid[i][j] = Integer.parseInt(str[j]);
            }
        }
        
        //DFS 탐색 모든 정점에서
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                dfs(i, j, "", 0); //정점위치 i,j , 문자열, 이동횟수
            }
        }
        
        //출력
        System.out.println(set.size());
    }
    
    private static void dfs(int x, int y, String path, int depth){
        
        if(depth == 6){ //6자리
            set.add(path);
            return;
        }
        
        //현재 위치의 숫자를 문자열에 추가
        path += grid[x][y];
        
        //네 방향으로 이동 (위, 아래, 오른, 왼)
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            //grid내에 위치하는지 체크 -> 계속 dfs탐색
            if(nx >= 0 && nx < 5 && ny >= 0 && ny < 5){
                dfs(nx, ny, path, depth+1);
            }
        }
    }
}