[JAVA] 2210번 - 숫자판 점프

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

문제 아이디어)

DFS를 쓰면 될 것같다.

그리고 길이가 6일때 DFS를 종료하고 중복되는 숫자들을 제거하고 가능한 경우의 수를 출력하면 될 것 같다.

** 원래는 dfs를 할때, 방문배열도 만드는데 여기서는 갔던 곳을 다시 가야하니까 방문배열은 없어도 된다

 

 

시간복잡도

DFS로 풀었고, 인접행렬로 구현했다. 

숫자판이 총 25칸이 있고 5*5이므로 모두 방문해야한다.

4가지 경우의 이동을 5번 하므로, 모든 경우를 탐색하면4^5만큼 경우의수 가능

시작위치경우 25 가지 * 이동 경우의 수

약 25600가지의 경우의 수 이다  

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. DFS함수 호출

필요한 파라미터는 x,y외에도 길이, 현재 문자열을 넣어준다.

private static void dfs(int x, int y, int len, String current) {
}

 

제일 처음은 이렇게 호출해서 시작한다.

dfs(i,j,0, "");

 

 

 

2. DFS 함수 내부 

1) current에 현재 숫자를 넣어준다

2) 상하좌우 탐색하면서 dfs를 재귀호출하면서 탐색해나가면서 해당 칸의 숫자를 current에 계속 추가한다

3) 그러다가 길이가 6이 되면 함수를 종료한다

private static void dfs(int x, int y, int len, String current) {
		current+=arr[x][y];
		if(len==5) {
			num.add(current);
			return;
		}
		
		//상하 좌우 탐색
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx>=0 && ny>=0 && nx<5 && ny<5) {
				dfs(nx,ny,len+1, current);
			}
		}
	}

 

 

3. 중복제거

자바에서는 중복제거할때 HashSet을 쓴다.

처음에는 StringBuilder에 담았는데, 중복제거가 필요했기에 HashSet으로 변경했다.

만들어지는 6자리 숫자들을 HashSet에 모두 담아두고 size를출력하면 자동으로 중복제거가 된다 

System.out.println(num.size());

 

 

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	static int[][] arr;
	static int ans =0;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};

	static Set<String> num;
	   public static void main(String[] args) throws IOException {
	        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        StringTokenizer st;

	        arr = new int[5][5];

	        for(int i=0; i<5; i++) {
	        	st = new StringTokenizer(br.readLine());
	        	for(int j=0; j<5; j++) {
	        		arr[i][j] = Integer.parseInt(st.nextToken());
	        	}        
	        }
	        
	        num = new HashSet<>();
	        for(int i=0; i<5; i++) {
	        	for(int j = 0; j<5; j++) {
	        		dfs(i,j,0, "");	 

	        	}
	        }
	        System.out.println(num.size());
	}
	   
	private static void dfs(int x, int y, int len, String current) {
		current+=arr[x][y];
		if(len==5) {
			num.add(current);
			return;
		}
		
		//상하 좌우 탐색
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx>=0 && ny>=0 && nx<5 && ny<5) {
				dfs(nx,ny,len+1, current);
			}
		}
	}
}