[BOJ] 20166.문자열 지옥에 빠진 호석
백준 알고리즘 문제 풀이
해당 문제는 제한 조건이 있었기 때문이라도 완전 탐색 활용하여 풀어보았습니다.
링크 : 
1. 문제
문제 보기
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 | 512 MB |
하루 종일 내리는 비에 세상이 출렁이고 구름이 해를 먹어 밤인지 낮인지 모르는 어느 여름 날
잠 들기 싫어 버티던 호석이는 무거운 눈꺼풀에 패배했다. 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다.
- 이 세상은 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 개의 문자열이 주어졌을 때, 호석이가 대답해야 하는 정답을 구해주도록 하자.
입력(Input)
첫번째 줄에 격자의 크기 N, M과 신이 좋아하는 문자열의 개수 K 가 주어진다.
다음에 N개의 줄에 걸쳐서 M개의 알파벳 소문자가 공백없이 주어진다. 여기서의 첫 번째 줄은 1행의 정보이며, N 번째 줄은 N행의 정보이다.
이어서 K개의 줄에 걸쳐서 신이 좋아하는 문자열이 주어진다. 모두 알파벳 소문자로 이루어져 있다.
출력(Output)
K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다.
제한
- 3 ≤ N, M ≤ 10, N과 M은 자연수이다.
- 1 ≤ K ≤ 1,000, K는 자연수이다.
- 1 ≤ 신이 좋아하는 문자열의 길이 ≤ 5
- 신이 좋아하는 문자열은 중복될 수도 있다.
2. 문제 풀이
신이 좋아하는 문자열 길이가 5 이하이고, N과 M, K의 수가 크지 않기 때문에 완전 탐색을 통해서 문제를 풀어볼 수 있을것 같았다.
우선 상, 하, 좌, 우 의 4방향뿐만 아니라 대각선으로도 가는 8방향으로 갈 수 있다고 나와 있다.
심지어 왔던 방향을 돌아가서 문자열을 만들 수 있으니 왔던 방향을 체크해주지 않아도 된다.
때문에 큐를 이용해서 반복적으로 큐에 넣고, 큐에 들어간 문자가 신이 좋아하는 문자열과 같으면 카운트를 올려주는 방식으로 풀 수 있다고 생각했다.
클래스를 하나 정의해서 큐에 넣어주고 다시 꺼낼 때 현재의 위치와 이동 가능 방향으로 이동하여 문자열을 만들 수 있도록 정의 한다.
// 큐에 들어가는 클래스
class Words
int x, y, len;
String str;
문자열의 길이가 5이기 때문에 길이 5가 넘어가면 더 이상 큐에 넣지 않고, 다시 큐에서 다음 Words를 꺼내는 식으로 조건을 건다.
a -> 길이가 5가 넘는지 체크 -> 신이 좋아하는 문자열이 있는지 체크, 있다면 카운팅 -> 8방향으로 보고 뒤에 문자열 추가 -> (큐에 넣기) -> 다시 차례가 와서 꺼내고 (반복)
위와 같은 반복을 통해 전부 다 돌려보도록해서 문제를 풀 수 있었다.
그럼 이것을 활용하여 코드로 표현해보자.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Hellhoseok_20166 {
static int N, M, K;
static char[][] cloud;
static int[][] dir = { // 배열 상, 하, 좌, 우, 좌상, 우상, 좌하, 우하
{-1, 1, 0, 0, -1, -1, 1, 1},
{0, 0, -1, 1, -1, 1, -1, 1}
};
static int[] result;
public static void solution(int x, int y, String[] keywords) {
Queue<Words> q = new LinkedList<>();
q.add(new Words(x, y, 1, cloud[x][y]+""));
while(!q.isEmpty()) {
Words tmpW = q.poll();
if(tmpW.len > 5) continue;
for(int j = 0; j < K; j++) {
if(keywords[j].equals(tmpW.str)) {
result[j]++;
}
}
for(int i = 0; i < 8; i++) {
int nx = tmpW.x + dir[0][i];
int ny = tmpW.y + dir[1][i];
if(nx == 0) nx = N;
if(ny == 0) ny = M;
if(nx > N) nx = 1;
if(ny > M) ny = 1;
q.add(new Words(nx, ny, tmpW.len + 1, tmpW.str + cloud[nx][ny]));
}
}
}
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());
cloud = new char[N + 1][M + 1];
result = new int[K];
String tmp = "";
for(int i = 1; i <= N; i++) {
tmp = br.readLine();
for(int j = 1; j <= M; j++) {
cloud[i][j] = tmp.charAt(j - 1);
}
}
String[] keywords = new String[K];
for(int i = 0; i < K; i++) {
tmp = br.readLine();
keywords[i] = tmp;
}
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
solution(i, j, keywords);
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < K; i++) {
sb.append(result[i] + "\n");
}
System.out.println(sb.toString());
}
}
class Words {
int x;
int y;
int len;
String str;
public Words(int x, int y, int len, String str) {
this.x = x;
this.y = y;
this.len = len;
this.str = str;
}
}
