백준 20166 문자열 지옥에 빠진 호석이 Kotlin (dfs)

문제 출처 : https://www.acmicpc.net/problem/20166

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

문제

하루 종일 내리는 비에 세상이 출렁이고 구름이 해를 먹어 밤인지 낮인지 모르는 어느 여름 날

잠 들기 싫어 버티던 호석이는 무거운 눈꺼풀에 패배했다. 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다.

• 이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자.
• 너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다.
• 시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이어 붙여서 문자열을 만들 수 있다.
• 이 곳의 신인 내가 좋아하는 문자열을 K 개 알려줄 터이니, 각 문자열 마다 너가 만들 수 있는 경우의 수를 잘 대답해야 너의 세계로 돌아갈 것이다.
• 경우의 수를 셀 때, 방문 순서가 다르면 다른 경우이다. 즉, (1,1)->(1,2) 로 가는 것과 (1,2)->(1,1) 을 가는 것은 서로 다른 경우이다.

호석이는 하늘을 보고서 "환형이 무엇인지는 알려달라!" 며 소리를 지르니 핏빛 구름이 흩어졌다가 모이며 아래와 같은 말을 그렸다.

• 너가 1행에서 위로 가면 N 행으로 가게 되며 반대도 가능하다.
• 너가 1열에서 왼쪽으로 가면 M 열로 가게 되며 반대도 가능하다.
• 대각선 방향에 대해서도 동일한 규칙이 적용된다.
• 하늘에 아래와 같은 그림을 구름으로 그려줄 터이니 이해해 돕도록 하여라.
• 예를 들어서, 너가 (1, 1)에서 위로 가면 (N, 1)이고, 왼쪽으로 가면 (1, M)이며 왼쪽 위 대각선 방향으로 가면 (N, M)인 것이다.

세상을 이루는 격자의 정보와, K 개의 문자열이 주어졌을 때, 호석이가 대답해야 하는 정답을 구해주도록 하자.

입력

첫번째 줄에 격자의 크기 N, M과 신이 좋아하는 문자열의 개수 K 가 주어진다.

다음에 N개의 줄에 걸쳐서 M개의 알파벳 소문자가 공백없이 주어진다. 여기서의 첫 번째 줄은 1행의 정보이며, N 번째 줄은 N행의 정보이다.

이어서 K개의 줄에 걸쳐서 신이 좋아하는 문자열이 주어진다. 모두 알파벳 소문자로 이루어져 있다.

출력

K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다.

제한

• 3 ≤ N, M ≤ 10, N과 M은 자연수이다.
• 1 ≤ K ≤ 1,000, K는 자연수이다.
• 1 ≤ 신이 좋아하는 문자열의 길이 ≤ 5
• 신이 좋아하는 문자열은 중복될 수도 있다.

출처

Contest > 류호석배 알고리즘 코딩 테스트 > 제1회 류호석배 알고리즘 코딩 테스트 3번

• 문제를 검수한 사람: BaaaaaaaaaaarkingDog, dlstj0923, tony9402
• 문제를 만든 사람: rhs0266

알고리즘 분류

• 그래프 이론
• 자료 구조
• 문자열
• 그래프 탐색
• 깊이 우선 탐색
• 해시를 사용한 집합과 맵

풀이

예제를 증명하려 손으로 경우의 수를 세어보다가 때려치고 맞겠거니 한 풀이로 풀었다.

우선 호석이는 상하좌우, 대각4방향 총8방향으로 움직일 수 있는데, 지렁이게임마냥 칸을 밟을 때마다 칸에 있는 알파벳을 추가하여 문자열을 늘려나간다.

호석이의 무빙은 dfs로 구현할 수 있다.

호석이가 움직이면서 만드는 문자열은 신이 원하는 문자열의 최대 길이만큼만 만들면 되고,

지나가면서 만들어지는 문자열마다 map에 개수를 증가시킨다.

호석이가 칸을 나가는 경우는 행의 크기가 n 열의 크기가 m이라 할 때, (i+n)%n, (i+m)%m으로 구현할 수 있다.

또한 같은 경로로 만들어진 문자열은 dfs를 같은 칸에서 시작하지 않는 이상 없기 때문에, 그래프의 모든 칸에서 dfs를  신이 원하는 문자열의 최대 길이만큼만 돌리면 된다!

 

코드

import kotlin.math.*
import java.util.*

val dir = arrayOf(
    intArrayOf(0,1),
    intArrayOf(0,-1),
    intArrayOf(1,0),
    intArrayOf(-1,0),
    intArrayOf(1,1),
    intArrayOf(-1,-1),
    intArrayOf(-1,1),
    intArrayOf(1,-1))

fun dfs(graph : Array<String>, map : MutableMap<String,Int>,n : Int, m : Int, maxK : Int, r : Int, c : Int,str : String){
    map.put(str,map.getOrDefault(str,0)+1)
    
    if(str.length==maxK)return

    for(i in dir.indices){
        var nR = (r+dir[i][0]+n)%n
        var nC = (c+dir[i][1]+m)%m
        dfs(graph,map,n,m,maxK,nR,nC,str+graph[nR][nC])
    }

}

fun makeMap(graph : Array<String>, map : MutableMap<String,Int>,n : Int, m : Int, maxK : Int){
    for(i in graph.indices){
        for(j in graph[i].indices){
            //각 시작점마다 dfs로 경로에 따라 생성되는 문자열 map에 저장
            //시작점이 다르므로 모두 다른 경로로 만들어진 문자열임
            dfs(graph,map,n,m,maxK,i,j,""+graph[i][j])
        }
    }
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    var tk = StringTokenizer(br.readLine())
    val (n,m,k) = List(3){Integer.parseInt(tk.nextToken())}
    //그래프 입력
    val graph = Array<String>(n){""}
    for(i in 0 until n){
        graph[i]=br.readLine()
    }
    //신의 문자열 입력 및 이중 최대 길이 추출
    val godStr = Array<String>(k){""}
    var maxK = 0
    for(i in 0 until k){
        godStr[i] = br.readLine()
        maxK = max(maxK,godStr[i].length)
    }
    //map에 이동경로에 따른 문자열의 개수를 저장
    val map = mutableMapOf<String,Int>()
    makeMap(graph,map,n,m,maxK)

    for(i in 0 until k){
        if(map[godStr[i]]==null)
            write("0\n")
        else
            write("${map[godStr[i]]}\n")
    }

    close()
}