[JAVA] 백준 20166번 【G4.문자열 지옥에 빠진 호석】

문제

20166번: 문자열 지옥에 빠진 호석

---

풀이

 

1️⃣ 백트래킹과 map을 이용한 풀이

이 문제는 백트래킹과 해시를 통해 문제를 해결하였다.

 

백트래킹을 통해서 만들 수 있는 문자열의 조합별 개수를 기록하였는데,

 

경로가 다르면 다른 경우의 수로 치기 때문이다.

 

백트래킹을 map의 각 포인트에서 시작하도록 설정하였고 탈출 조건을 설정한 길이에 도달했을 때 기록하는 방식을 사용했다.

 

왜냐하면, 예를 들어 (1,1) 에서 시작해서 길이가 2를 만족할때의 경우의 수는 다른 포인트에서 시작한 길이가 2인 경우와 절대 중복이 발생하지 않을 것이라 판단했기 때문이다.

 

 

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

public class Main {
    static int N;
    static int M;
    static int K;
    static String[][] map;

    static int[] dr = {1, 1, 1, 0, 0, -1, -1, -1};
    static int[] dc = {1, 0, -1, 1, -1, -1, 0, 1};
    static HashMap<String, Integer> hashMap = new HashMap<>();
    static Stack<String> s = new Stack<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        setUp(br);
        getCntOfCombination();
        getAnswer(br);


    }
    
    private static void setUp(BufferedReader br) throws IOException {
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        N = input[0];
        M = input[1];
        K = input[2];

        map = new String[N][M];

        for (int r = 0; r < N; r++) {
            String[] info = br.readLine().split("");
            for (int c = 0; c < M; c++) {
                map[r][c] = info[c];
            }
        }
    }

    private static void getCntOfCombination() {
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                for (int length = 1; length <= 5; length++) {
                    s.push(map[r][c]);
                    bt(r, c, length);
                    s.clear();
                }
            }
        }
    }

    private static void bt(int r, int c, int length) {
        if (s.size() == length) {
            String result = convertStackToString();
            hashMap.put(result, hashMap.getOrDefault(result, 0) + 1);
            return;
        }

        for (int i = 0; i < 8; i++) {
            int nr = (dr[i] + r + N) % N, nc = (dc[i] + c + M) % M;
            s.push(map[nr][nc]);
            bt(nr, nc, length);
            s.pop();
        }
    }

    private static String convertStackToString() {
        StringBuilder sb = new StringBuilder();
        for (String str : s) {
            sb.append(str);
        }
        return sb.toString();
    }

    private static void getAnswer(BufferedReader br) throws IOException {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < K; i++) {
            sb.append(hashMap.getOrDefault(br.readLine(), 0) + "\n");
        }
        System.out.println(sb);
    }

    
}

 

결과

 

 

 

백트래킹을 잘 구현할 수 있다면 크게 어렵지 않은 문제였다.