생각정리/코딩테스트
[JAVA 알고리즘]BAEKJOON 20166번 문자열 지옥에 빠진 호석
생각중임
2024. 1. 4. 17:48
다이나믹 프로그래밍을 이용해서 문제를 해결하는 문제
문자열 지옥에 빠진 호석
문제 설명
하루 종일 내리는 비에 세상이 출렁이고 구름이 해를 먹어 밤인지 낮인지 모르는 어느 여름 날
잠 들기 싫어 버티던 호석이는 무거운 눈꺼풀에 패배했다. 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다.
- 이 세상은 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
- 신이 좋아하는 문자열은 중복될 수도 있다.
입출력 예
| input | return |
| 3 3 2 aaa aba aaa aa bb |
56 0 |
| 3 4 3 abcb bcaa abac aba abc cab |
66 32 38 |
나의 문제풀이
import java.io.*;
import java.util.*;
public class Main {
static String[][] map;
static String[] godStr;
static Map<String, Integer> godCases = new HashMap<>();
static int N, M, K;
static int[] dx = {-1, 1, 0, 0, 1, 1, -1, -1};
static int[] dy = {0, 0, -1, 1, 1, -1, 1, -1};
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
N = Integer.parseInt(stringTokenizer.nextToken());
M = Integer.parseInt(stringTokenizer.nextToken());
K = Integer.parseInt(stringTokenizer.nextToken());
// 주어진 격자공간을 이차배열로 만들어준다.
map = new String[N][M];
for (int i = 0; i < N; i++) {
String[] array = bufferedReader.readLine().split("");
for (int j = 0; j < M; j++) {
map[i][j] = array[j];
}
}
// 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 확인하기 위해 map 사용
godStr = new String[K];
int max = 0;
for (int i = 0; i < K; i++) {
godStr[i] = bufferedReader.readLine();
godCases.put(godStr[i], 0);
max = Math.max(max, godStr[i].length());
}
bufferedReader.close();
// 위치별로 움직임 반복
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
dfs(i, j, map[i][j], max);
}
}
// 경우의 수 출력
for (String str : godStr) {
System.out.println(godCases.get(str));
}
}
public static void dfs(int x, int y, String str, int max) {
// 문자열에 포함이 되어 있으면 경우의 수 체크
if (godCases.containsKey(str)) {
godCases.put(str, godCases.get(str) + 1);
}
// 문자열 크기에 도착하면 종료
if (str.length() == max) {
return;
}
// 상하좌우 대각선을 반복하면서 이동한다.
for (int i = 0; i < dx.length; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
if (nextX < 0) nextX = N - 1;
if (nextY < 0) nextY = M - 1;
if (nextX == N) nextX = 0;
if (nextY == M) nextY = 0;
dfs(nextX, nextY, str + map[nextX][nextY], max);
}
}
}- 입력값을 이차배열에 넣어준다.
- 입력한 문자열을 확인할 배열과 문자열의 경우의 수를 헤아릴 맵컬렉션에 문자열을 넣어준다.
- 입력받는 문자열이 다를 수 있어 가장 긴 문자열의 길이를 확인한다.
- 아무 곳에서 시작하기 때문에 모든 위치에서 움직임을 반복한다.
- 상하좌우 대각선 4방향 모두 반복하면서 이동한다.
- 배열의 크기에서 벗어나면 반대편에서 시작하기 때문에 0보다 작으면 배열의 마지막 크기로 배열의 크기보다 커지면 0으로 이동위치를 수정해 준다.
- 만들어진 문자열이 신의 문자열에 포함이 되어 있으면 경우의 수를 더해준다.
- 가장 긴 문자열의 길이만큼 반복했으면 종료한다.
- 확인된 경우의 수를 출력한다.
처음에는 다른 문제들과 같이 visited를 만들어 움직임을 체크해서 중복을 안되도록 하려고 했는데, 문제의 조건에서 방문 순서가 다르면 다른 경우로 나오기 때문에 오히려 할 필요가 없었다.
처음에는 예시에서 주어진 문자열이 모두 길이가 같아서 하나의 신이 좋아하는 문자열의 길이만 체크해서 종료가 되도록 했는데, 부분 점수로 2개의 반례가 있어 확인을 하다가 다른 사람들 풀이를 참조해 보니, 문자열의 길이가 다를 경우가 있어 그냥 최고 문자열의 길이로 5로 해서 반복을 하면 되지만 조금이라도 효율적이게 하기 위해서 해당 주어진 문자열들의 길이중 가장 긴 길이만큼만 반복을 하도록 한걸 참고했다.