알고리즘/BOJ

백준 1189번 컴백홈

꾸준함. 2024. 3. 27. 00:01

문제 링크입니다: https://www.acmicpc.net/problem/1189

 

1189번: 컴백홈

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다

www.acmicpc.net

 

R, C, K 범위가 작기 때문에 완전탐색으로 풀어도 되는 문제였습니다.

 

#include <iostream>
#include <string>
using namespace std;
const int MAX = 5;
typedef struct
{
int y, x;
} Dir;
Dir moveDir[4] = { {1,0 }, {-1, 0}, {0, 1}, {0, -1} };
int R, C, K;
int result = 0;
string board[MAX];
bool visited[MAX][MAX];
void func(int y, int x, int cnt)
{
if (y == 0 && x == C - 1 && cnt == K - 1)
{
result++;
return;
}
for (int k = 0; k < 4; k++)
{
int nextY = y + moveDir[k].y;
int nextX = x + moveDir[k].x;
if (nextY < 0 || nextY >= R || nextX < 0 || nextX >= C)
{
continue;
}
if (visited[nextY][nextX] || board[nextY][nextX] == 'T')
{
continue;
}
visited[nextY][nextX] = true;
func(nextY, nextX, cnt + 1);
visited[nextY][nextX] = false;
}
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> R >> C >> K;
for (int y = 0; y < R; y++)
{
cin >> board[y];
}
visited[R - 1][0] = true;
func(R - 1, 0, 0);
cout << result << "\n";
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1285번 동전 뒤집기  (0) 2024.03.30
백준 19942번 다이어트  (1) 2024.03.30
백준 14620번 꽃길  (0) 2024.03.26
백준 9934번 완전 이진 트리  (0) 2024.03.26
백준 14497번 주난의 난(難)  (0) 2024.03.23