Machineboy空
1189: 컴백홈 - DFS 본문
https://www.acmicpc.net/problem/1189
문제요약
왼쪽 아래에서 오른쪽 위 꼭짓점으로 이동할 때, 이동 거리가 k인 경우의 수 구하기
난이도
Silver 1
풀이 포인트
- 경로의 수 누적하기
- 방문배열 초기화 위치
REVIEW
방문배열에 이동 거리를 누적해 가는 방법에 익숙해 져야 하고,
재귀가 끝나는 시점에 방문배열을 초기화해줘야 하는데, 이 코드의 위치를 찾기가 힘들었다.
한 경로가 끝이나면 방문 배열을 초기화해주고 또 새로운 경로를 탐색토록 해야하는데,
이것이 재귀로 뻗어나가니 실행순서를 파악하는 것이 참 헷갈렸다.
아직까진 bfs보다 dfs구현이 쉬워서 기본 코드는 이제 외운듯 하나,
이렇게 활용이 들어가면 자꾸 헤메니 아직 실력이 너무 부족하다..
대충의 감은 온 것 같다.
CODE
#include<bits/stdc++.h>
using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, k, visited[10][10];
char a[10][10];
string s;
int go(int y, int x){
// 한 경로가 도착지에 다다랐고, k번째 만에 이동했다면 1가지 경우의 수 추가
if(y == 0 && x == m - 1){
if(k == visited[y][x]) return 1;
return 0;
}
// k만에 가는 경로의 수 누적
int ret = 0;
// 일반 DFS
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx] || a[ny][nx] == 'T')continue;
// 방문배열에 이동 거리 누적
visited[ny][nx] = visited[y][x] + 1;
// 현재 탐색하는 경로 중 k번째 이동에 성공하면 1이 리턴값으로 누적
ret += go(ny, nx);
// 현재 탐색 끝나고 방문배열 초기화
visited[ny][nx] = 0;
}
return ret;
}
int main(){
cin >> n >> m >> k;
for(int i = 0; i < n; i++){
cin >> s;
for(int j = 0; j < m; j++){
a[i][j] = s[j];
}
}
visited[n - 1][0] = 1;
cout << go(n - 1, 0) << "\n";
}
'Computer > Coding Test' 카테고리의 다른 글
14497 : 주난의 난 - bfs, dfs (0) | 2024.04.01 |
---|---|
14620 : 꽃길 - dfs (0) | 2024.03.28 |
17071: 숨바꼭질 5 (0) | 2024.03.20 |
13913 숨바꼭질 4 : bfs (1) | 2024.03.18 |
12851 : 숨바꼭질 2 - BFS (1) | 2024.02.29 |