백준 2210: 숫자판 점프 (java)

알고리즘

그래프: DFS

 

체감 난이도

★ ★ ★ ★ ☆

-> 나는 이동 문제에 많이 약한 것 같다 ..

 

다시 풀 수 있는가?

NO

---

 

1. 방향 이동

 

x, y 좌표 상에서 방향을 설정하여 이동하는 문제에서 자주 사용되니 꼭 기억해둘 것!

 

dx -> 상 / 하

dy -> 좌 / 우 기준이다.

 

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

 

2. HashSet 값 추가 과정

 

cnt가 5라는 것은 6개의 문자열이 다 찼다는 뜻이고,

이렇게 한 묶음을 HashSet에 추가해준다.

 

모든 탐색이 끝날 때까지 묶음이 HashSet에 추가되고, 나중에 size를 리턴해주면 끝!

 

        if (cnt == 5) {
            ans.add(tmp);
            return;
        }

 

3. 재귀 호출 (중요)

 

상하좌우 움직이면서 재귀적으로 호출한다.

배열 범위 안에서 움직여야하므로 조건을 설정해준다.

 

        for (int i = 0; i < 4; i++) {
            int currX = x+dx[i];
            int currY = y+dy[i];

            if ((0 <= currX && currX < 5) && (0 <= currY && currY < 5)) {
                dfs(arr, currX, currY, cnt+1, tmp+arr[currX][currY]);
            }
        }

 

 

전체 코드 ▼

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    String[][] arr = new String[5][5];
    HashSet<String> ans = new HashSet<>();

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

    public void dfs(String[][] arr, int x, int y, int cnt, String tmp) {
        if (cnt == 5) {
            ans.add(tmp);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int currX = x+dx[i];
            int currY = y+dy[i];

            if ((0 <= currX && currX < 5) && (0 <= currY && currY < 5)) {
                dfs(arr, currX, currY, cnt+1, tmp+arr[currX][currY]);
            }
        }
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < 5; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 5; j++) {
                arr[i][j] = st2.nextToken();
            }
        }

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                dfs(arr, i, j, 0, arr[i][j]);
            }
        }

        System.out.println(ans.size());
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}