이번에 풀어본 문제는
백준 20166번 문자열 지옥에 빠진 호석 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Point
{
    int x,y,len;
    String str;

    public Point(int x, int y, int len, String str) {
        this.x = x;
        this.y = y;
        this.len = len;
        this.str = str;
    }
}
public class Main {
    static int N,M,K;
    static char [][] map;
    static Map<String,Integer> hm;
    static int [] dx = {-1,-1,0,1,1,1,0,-1}; // 상부터 시계방향
    static int [] dy = {0,1,1,1,0,-1,-1,-1};
    static int maxLen = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        hm = new HashMap<>();

        for(int i = 0; i < N; ++i)
        {
            String input = br.readLine();
            for(int j = 0; j < M; ++j)
            {
                map[i][j] = input.charAt(j);
            }
        }

        String [] keys = new String[K];
        for(int i = 0; i < K; ++i)
        {
            // 좋아하는 문자열 해시맵에 0카운트로 put
            String input = br.readLine();
            //정답 출력을 위해 담아두기
            keys[i] = input;
            maxLen = Math.max(maxLen,input.length());
            hm.put(input,0);
        }

        for(int i = 0; i < N; ++i)
        {
            for(int j = 0; j < M; ++j)
            {
                makeString(i,j);
            }
        }
        StringBuilder sb = new StringBuilder();
        for(String s : keys)
        {
            sb.append(hm.get(s)).append("\n");
        }
        System.out.print(sb);
    }
    static void makeString(int x, int y)
    {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x,y,1,map[x][y]+""));

        while(!q.isEmpty())
        {
            Point cur = q.poll();

            //주어진 문자열 중 최대길이보다 길면 탐색중지
            if(cur.len > maxLen) continue;
            //일치하면 카운트 ++
            if(hm.containsKey(cur.str))
            {
                hm.put(cur.str,hm.get(cur.str)+1);
            }

            for(int idx = 0; idx < 8; ++idx)
            {
                int mx = (cur.x + dx[idx]) % N;
                int my = (cur.y + dy[idx]) % M;

                if(mx < 0) mx += N;
                if(my < 0) my += M;

                q.add(new Point(mx,my,cur.len+1,cur.str+map[mx][my]));
            }
        }
    }

}

📝 풀이

주어진 맵에서의 8방향 이동으로, 입력된 K개의 문자열을 몇 차례 만들 수 있는지 출력하는 문제입니다. 범위를 벗어나는 경우는 반대쪽으로 이동하게 됩니다.
먼저 신이 좋아하는 문자열은 해시맵에 담아줍니다. 해시맵을 사용하지 않으면 문자열의 일치 여부를 판단하기 위해 잦은 탐색이 필요할 것 같습니다. 또한 신이 좋아하는 문자열은 중복값이 입력될 수도 있기 때문에 해당 부분도 해시맵이 유리하다고 생각했습니다.
해시맵에 모든 키워드를 담았다면, 맵의 모든 위치를 시작점으로 bfs를 진행해줍니다. 별 다른 제약조건 없이 8방향으로 계속 뻗어나가며, 문자열을 만드는 과정에서 입력으로 주어진 키워드의 최대길이(문제에서 최대 5라고 했지만 저는 입력 받으면서 입력값의 최대길이를 maxLen 변수에 담아보았습니다.)를 초과한다면 탐색을 종료시켜줍니다. 큐에서 꺼낼 때 마다 해시맵에 해당 키워드가 존재하는 지 여부를 체크해주고, 해당 키값이 존재한다면 신이 좋아하는 문자열을 완성한 경우이기 때문에, 해당 키값에 대한 value를 1 증가시켜주면 됩니다.
마지막으로 K개의 신이 좋아하는 문자열을 담아두었던 keys 배열의 원소들을 키값으로 갖는 해시맵의 value들을 출력해주면, 해결할 수 있습니다.

📜 후기

구현은 금방 해냈지만 대각선으로 범위를 벗어날 때의 이동 위치가 너무 헷갈려서 해당 부분을 조금 참고했습니다. 항상 이런 조건에서는 범위를 벗어났을 때 방향을 반대로 뒤집어서 이동시키곤 했었는데, 위와 같은 처리 방법을 알게되어 다음에도 유용하게 활용할 수 있을 것 같네요!