[C++] 백준 1189번 컴백홈
문제
한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.
cdef ...f ..ef ..gh cdeh cdej ...f bT.. .T.e .Td. .Tfe bTfg bTfi .Tde a... abcd abc. abcd a... a.gh abc. 거리 : 6 6 6 8 8 10 6
위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.
입력
첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K < R*C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R x C 맵의 정보를 나타내는 .과 T로 구성된 길이가 C인 문자열이 주어진다.
출력
첫 줄에 거리가 K인 가짓수를 출력한다.
풀이
간단한 완전탐색 문제다. visited로 방문한 곳을 체크하고 목적지에 도달했을 때 거리가 k인 경우에만 세면 된다.
#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'
using namespace std;
int h,w,k;
string board[5];
int visited[5][5];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int solve(int len, int x, int y){
if (x == 0 && y == w-1){
if (len == k) return 1;
else return 0;
}
int ret = 0;
visited[x][y] = 1;
for (int i=0; i<4; i++){
int nx = x+dx[i];
int ny = y+dy[i];
if (nx < 0 || ny < 0 || nx >= h || ny >= w || board[nx][ny] == 'T') continue;
if (visited[nx][ny]) continue;
ret += solve(len+1,nx,ny);
}
visited[x][y] = 0;
return ret;
}
int main(){
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// ifstream cin;
// cin.open("input.txt");
cin >> h >> w >> k;
for (int i=0; i<h; i++)
cin >> board[i];
cout << solve(1,h-1,0);
}
Author And Source
이 문제에 관하여([C++] 백준 1189번 컴백홈), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lacram/C-백준-번-1ndox6i1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)