Machineboy空
1987 : 알파벳 - DFS, BFS 본문
https://www.acmicpc.net/problem/1987
문제요약
밟지 않은 새로운 알파벳 칸으로만 갈 수 있을 때, 이동할 수 있는 최대 칸
난이도
Gold 4
풀이 포인트
- DFS 활용
- 이전 글자와 중복 체크
REVIEW
아직 문제가 주어졌을 때, bfs와 dfs중 무엇을 선택해야할지 모르겠다.
dfs는 감이 오는데 bfs의 경우 아직 낯설다..
이 문제의 경우 string에 지나온 값들을 누적해주고 그것을 초기화할 시점을 잘못 짚어
모든 순회의 결과를 한 string에 누적하다보니 계속해서 오답이었다.
모범답안에서 재귀를 돌리고, 다음 순회에 관해서는 초기화하고
날을 잡고 dfs, bfs 디버깅을 깊게 해서 흐름을 좀 이해할 필요가 있음
CODE
#include <bits/stdc++.h>
using namespace std;
int R, C, ret, ny, nx, visited[30];
char a[21][21];
const int dy[] = {-1, 0, 1, 0};
const int dx[] = { 0, 1, 0, -1};
void go(int y, int x, int cnt){
ret = max(ret, cnt);
cout << "현재 ret은 " << ret <<'\n';
for(int i = 0; i < 4; i++){
ny = y + dy[i], nx = x + dx[i];
// 오버플로우 체크
if(ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
int next = (int)(a[ny][nx] - 'A');
if(visited[next] == 0){
visited[next] = 1;
cout << next << "가 새로운 글자라 넣겠다.\n";
go(ny, nx, cnt + 1);
//다음 순회에 대해선 또 초기화
visited[next] = 0;
}
}
return;
}
int main(){
cin >> R >> C;
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++){
cin >> a[i][j];
}
}
visited[(int)a[0][0] - 'A'] = 1;
go(0, 0, 1);
cout << ret << '\n';
return 0;
}
'Computer > Coding Test' 카테고리의 다른 글
11866: 요세푸스 문제 0 - queue (0) | 2024.06.07 |
---|---|
1931: 회의실 배정 - 그리디 (0) | 2024.06.07 |
14497 : 주난의 난 - bfs, dfs (0) | 2024.04.01 |
14620 : 꽃길 - dfs (0) | 2024.03.28 |
1189: 컴백홈 - DFS (0) | 2024.03.22 |