Notice
Recent Posts
Recent Comments
Link
«   2025/03   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
Tags
more
Archives
Today
Total
관리 메뉴

끄적끄적

백준 [20166] 문자열 지옥에 빠진 호석 본문

코테준비/백준

백준 [20166] 문자열 지옥에 빠진 호석

alstj_성공 2022. 8. 16. 22:14

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

 

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

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

www.acmicpc.net

 

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;
char grid[11][11];
unordered_map<string, int> m;
int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dy[8] = { 1, 1, 1, 0, 0, -1, -1, -1 };
int N, M, K;
void dfs(int x, int y, string cur) {
if (cur.length() > 5) return;
m[cur]++;
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= N) nx = 0;
else if (nx < 0) nx = N - 1;
if (ny >= M) ny = 0;
else if (ny < 0) ny = M - 1;
dfs(nx, ny, cur + grid[nx][ny]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> grid[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
s = grid[i][j];
dfs(i, j, s);
}
}
for (int i = 0; i < K; i++) {
cin >> s;
cout << m[s] << '\n';
}
return 0;
}
view raw 20166.cpp hosted with ❤ by GitHub

dfs+해시

아무곳에서나 시작할 수 있고, 방문순서가 다르면 다른 것이며, 이미 방문했던 곳도 다시 방문할 수 있으므로 방문배열을 사용하지 않고 각 위치에서 시작하는 dfs를 적용해준다.

환형탐색이므로 범위를 넘어서면 초기화해주는 작업이 필요하다.

'코테준비 > 백준' 카테고리의 다른 글

백준 [2589] 보물섬  (0) 2022.08.22
백준 [1012] 유기농 배추  (0) 2022.08.18
백준 [13904] 과제  (0) 2022.08.15
백준 [11000] 강의실 배정  (0) 2022.08.14
백준 [2002] 추월  (0) 2022.08.13