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

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

반응형

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

문제

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

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

이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자.

N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자. 너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다.

시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이어 붙여서 문자열을 만들 수 있다.

이 곳의 신인 내가 좋아하는 문자열을 K 개 알려줄 터이니, 각 문자열 마다 너가 만들 수 있는 경우의 수를 잘 대답해야 너의 세계로 돌아갈 것이다.

K 개 알려줄 터이니, 각 문자열 마다 너가 만들 수 있는 경우의 수를 잘 대답해야 너의 세계로 돌아갈 것이다. 경우의 수를 셀 때, 방문 순서가 다르면 다른 경우이다. 즉, (1,1)->(1,2) 로 가는 것과 (1,2)->(1,1) 을 가는 것은 서로 다른 경우이다.

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

너가 1행에서 위로 가면 N 행으로 가게 되며 반대도 가능하다.

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은 자연수이다.

N, M ≤ 10, N과 M은 자연수이다. 1 ≤ K ≤ 1,000, K는 자연수이다.

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, map : MutableMap,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, map : MutableMap,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(n){""} for(i in 0 until n){ graph[i]=br.readLine() } //신의 문자열 입력 및 이중 최대 길이 추출 val godStr = Array(k){""} var maxK = 0 for(i in 0 until k){ godStr[i] = br.readLine() maxK = max(maxK,godStr[i].length) } //map에 이동경로에 따른 문자열의 개수를 저장 val map = mutableMapOf() makeMap(graph,map,n,m,maxK) for(i in 0 until k){ if(map[godStr[i]]==null) write("0

") else write("${map[godStr[i]]}

") } close() }

반응형

from http://ongveloper.tistory.com/233 by ccl(A) rewrite - 2021-09-11 08:27:38