백준 20166 문자열 지옥에 빠진 호석 python, java

DFS 방식으로 이동하고 딕셔너리 (자바의 경우 해시맵)를 이용해서 만들어지는 모든 문자열을 카운트 했다.

📜 문제 바로 가기 : 문자열 지옥에 빠진 호석

제출코드

파이썬

import sys
input = sys.stdin.readline

def move(i, j, di, dj):
    return warp(i+di, N), warp(j+dj, M)

def warp(i, N):
    if i < 0 :
        return N-1
    elif i >= N:
        return 0
    return i

def recur(s, ni, nj, w):
    if dd.get(w) == None:
            dd[w] = 1
    else:
        dd[w] += 1

    if s == 4:
        return

    for di, dj in delta:
        i, j = move(ni, nj, di, dj)
        if (ni != i or nj != j):
            recur(s+1, i, j, w+arr[i][j])    

N, M, K = map(int, input().split())

arr = [input().rstrip() for _ in range(N)]

dd = {}
delta = [(0,1), (0,-1), (1,0), (-1,0), (1,1), (1,-1), (-1,-1),(-1,1)]

for i in range(N):
    for j in range(M):
        recur(0, i, j, arr[i][j])

for _ in range(K):
    s = input().rstrip()
    if dd.get(s) == None:
            print(0)
    else:
        print(dd[s])

자바

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

public class Main {
    static int N;
    static int M;
    static int K;
    static String[] arr;
    static int[][] delta = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
    static HashMap<String, Integer> dd = new HashMap<>();
    static boolean[][] visited;
    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());

        arr = new String[N];
        for (int i=0; i < N; i++) {
            arr[i] = br.readLine();
        }

        visited = new boolean[N][M];

        for (int i = 0; i < N; i ++) {
            for (int j = 0; j < M; j ++) {
                StringBuilder w = new StringBuilder(String.valueOf(arr[i].charAt(j)));
                recur(0, i, j, w);
            }
        }
        for (int i =0; i < K; i ++) {
            System.out.println(dd.getOrDefault(br.readLine(), 0));
        }

    };
    
    public static void recur(int s, int ni, int nj, StringBuilder w) {
        if (dd.containsKey(w.toString()) == false) {
            dd.put(w.toString(), 1);
        } else {
            dd.put(w.toString(), dd.get(w.toString()) + 1);
        }

        if (s == 4) {
            return ;
        }

        visited[ni][nj] = true;

        for (int idx = 0; idx < 8; idx ++) {
            int[] pos = move(ni, nj, delta[idx][0], delta[idx][1]);
            if (pos[0] != ni || pos[1] != nj) {
                Character tmpChar = arr[pos[0]].charAt(pos[1]);
                recur(s+1, pos[0], pos[1], new StringBuilder(w.toString()).append(String.valueOf(tmpChar)));
            }
        }
    }
    
    public static int[] move(int i, int j, int di, int dj) {
        return new int[]{wrap(i + di, N), wrap(j + dj, M)};
    }
    
    public static int wrap(int i, int n) {
        if (i < 0) {
            return n-1;
        } else if (i >= n) {
            return 0;
        }
        return i;
    }

}

---

접근방법

wrap() 메소드를 통해 경계값처리를 해주었고 recur() 메소드를 통해 DFS방식을 구현했다.

한가지 주의해야 할점은 처음엔 중복 방문이 가능하고 방문순서가 다르면 경우의 수가 다르게 카운트 되기때문에 처음에는 조건없이 단순히 8방향 델타로 이동시켰지만, N = 1, M = 3 배열 "aaa" 의 경우 (0,0) 에서 위로가던 아래로가던 (0,0) 으로 돌아오기 때문에 (0,0) -> (0,0) 이런 경우를 피하기 위해
(ni != i or nj != j) 이러한 조건을 추가 시켜줘야 한다.