[C++] 백준(BOJ) - 1103 : 게임
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.
일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.
- 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
- 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
- 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.
만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.
보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.
입력
줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.
알고리즘
- DFS
- DP
풀이
- 보드 판의 숫자만큼 움직인다
- 구멍 or 보드판 벗어나면 종료
- Cycle이 생기는 경우 -1 반환하고 메인함수 종료
- 방문처리 배열로 처리 가능
- DP 배열
- 메모이제이션으로 속도 향상 가능
코드
// BOJ - 1103 : 게임
#include<bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0 ,1, 0 ,-1 };
int n, m, a[54][54], visited[54][54], dp[54][54];
bool in(int aa, int bb)
{
return (aa >= 0 && aa < n && bb >= 0 && bb < m);
}
int dfs(int y, int x)
{
if (!in(y, x) || a[y][x] == -1) return 0;
if (visited[y][x])
{
cout << -1 << '\n';
exit(0); // 메인함수 종료
}
int& res = dp[y][x];
if (res) return res;
visited[y][x] = 1;
int value = a[y][x];
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i] * value;
int nx = x + dx[i] * value;
res = max(res, dfs(ny, nx) + 1);
}
visited[y][x] = 0; // 다음 경우의 수에 영향 없게 방문처리 함수 원복
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
string str;
cin >> str;
for (int j = 0; j < str.size(); j++)
{
if (str[j] == 'H') a[i][j] = -1;
else a[i][j] = str[j] - '0';
}
}
cout << dfs(0, 0) << '\n';
return 0;
}
평가
- 간단한 int형 dfs 문제
- DP와 메모이제이션을 활용하여 코드 속도 최적화 가능
- cyclic한 구조는 무한루프에 빠질 수 있으니
exit(0)을 활용해 메인 함수 종료가 필요 - 완전탐색은 방문처리 check, 메인로직, uncheck 꼴로 이루어 진다는 것 다시 확인
