끄적끄적
백준 [20166] 문자열 지옥에 빠진 호석 본문
출처 : https://www.acmicpc.net/problem/20166
20166번: 문자열 지옥에 빠진 호석
K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다.
www.acmicpc.net
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
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 |