문제 링크입니다: 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 범위가 작기 때문에 완전탐색으로 풀어도 되는 문제였습니다.
This file contains hidden or 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 <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; | |
} |

개발환경: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 |