[백준] 20166번 - 문자열 지옥에 빠진 호석 / C++

문제

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

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

• 이 세상은 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
• 신이 좋아하는 문자열은 중복될 수도 있다.

 

코드

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

struct pos
{
	int r;
	int c;
};

int N;
int M;
int K;
string board[10];
unordered_map<string, int> cnt;

bool in_range(pos p)
{
	if (p.r < 0 || p.r >= N || p.c < 0 || p.c >= M)
		return false;
	return true;
}

pos get_pos(pos curr, int d)
{
	int dr[] = {-1, -1, 0, 1, 1, 1, 0, -1};
	int dc[] = {0, 1, 1 ,1, 0, -1, -1, -1};
	pos next;

	// 다음 좌표 계산
	next.r = curr.r + dr[d];
	next.c = curr.c + dc[d];
	// 범위를 벗어나는 경우
	if (next.r < 0)		next.r = N - 1;
	if (next.r >= N) 	next.r = 0;
	if (next.c < 0)		next.c = M - 1;
	if (next.c >= M)	next.c = 0;
	return next;
}

void dfs(pos curr, string s)
{
	int i;

	// 현재 좌표의 문자 추가
	s += board[curr.r][curr.c];
	cnt[s]++;
	// 최대 길이만큼 확인한 경우 리턴
	if (s.size() == 5)
		return;
	// 모든 방향에 대해 dfs 수행
	for (i = 0; i < 8; i++)
		dfs(get_pos(curr, i), s);
}

int main()
{
	int i;
	string s;
	pos p;

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K;
	for (i = 0; i < N; i++)
	{
		cin >> board[i];
	}
	// 모든 좌표에서 시작하여 만들 수 있는 모든 문자열을 확인
	for (p.r = 0; p.r < N; p.r++)
	{
		for (p.c = 0; p.c < M; p.c++)
		{
			dfs(p, "");
		}	
	}
	// 입력받은 문자열을 만들 수 있는 경우의 수를 출력
	for (i = 0; i < K; i++)
	{
		cin >> s;
		cout << cnt[s] << "\n";
	}
	return 0;
}

 

 

DFS로 탐색하는 과정에서 출발지가 다르기 때문에 탐색하는 모든 문자열은 다른 경우로 인정된다. 신이 좋아하는 문자열의 길이가 1~5이기 때문에 문자를 이어 붙일 때마다 경우의 수를 더해주어야 한다. 각 문자열에 대한 경우의 수는 해시맵에 저장한다.

 

링크

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

inbdni/Baekjoon