이번에는 백준 1103번 게임 문제를 풀어보았습니다.
현재 칸에 적힌 숫자만큼 상하좌우로 이동하면서 최대 이동 횟수를 구해야 하는 문제입니다. 단순 DFS로 모든 경우를 탐색하면 같은 위치에서 시작하는 경우를 계속 다시 계산하게 되므로 dp를 함께 사용하였습니다.
또한 현재 DFS 경로에서 이미 방문한 위치를 다시 방문할 수 있다면 같은 이동을 계속 반복할 수 있으므로 무한히 움직일 수 있습니다. 이를 visited 배열을 이용하여 사이클 여부를 확인하였습니다.
문제 설명
동전은 (0, 0)에서 시작합니다.
현재 위치에 적힌 숫자가 X라면 상하좌우 중 하나를 선택하여 정확히 X칸 이동합니다.
이동한 결과가
보드 바깥
구멍(H)이라면 게임이 종료됩니다.
게임을 최대한 오래 진행했을 때 이동할 수 있는 최대 횟수를 구해야 합니다.
하지만 이동 과정에서 사이클이 만들어진다면 같은 경로를 무한히 반복할 수 있으므로 -1을 출력해야 합니다.
풀이 아이디어
현재 위치 (y, x)에서 시작했을 때 최대 몇 번 움직일 수 있는지를
dp[y][x]에 저장합니다.
현재 칸의 숫자가 X라면 다음 위치는 네 방향에 대해
(y + dy[i] × X, x + dx[i] × X)가 됩니다.
각 방향으로 이동한 결과에 대해 DFS를 수행하고
1 + dfs(다음 위치)중 가장 큰 값을 dp[y][x]에 저장합니다.
여기서 1은 현재 위치에서 다음 위치로 이동한 한 번을 의미합니다.
동시에 visited[y][x]를 이용하여 현재 DFS 경로에서 방문 중인 위치를 관리합니다.
DFS를 진행하다가 visited[y][x] == 1인 위치를 다시 만난다면 현재 경로 내부에서 사이클이 발생한 것이므로 cycle = true로 설정합니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N,M;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
int arr[50][50], visited[50][50];
int dp[50][50];
bool cycle;
int dfs(int y, int x) {
if (y >= N || x >= M || y < 0 || x < 0 || arr[y][x] == -1) {
return 0;
}
if (visited[y][x]) {
cycle = true;
return 0;
}
if (dp[y][x] != -1) {
return dp[y][x];
}
visited[y][x] = 1;
dp[y][x] = 0;
for (int i=0; i<4; i++) {
int ny = y + dy[i] * arr[y][x];
int nx = x + dx[i] * arr[y][x];
dp[y][x] = max(dp[y][x], 1 + dfs(ny,nx));
}
visited[y][x] = 0;
return dp[y][x];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
memset(dp, -1, sizeof(dp));
cin >> N >> M;
for (int i=0; i<N; i++) {
string temp;
cin >> temp;
for (int j=0; j<M; j++) {
if (temp[j] != 'H')
arr[i][j] = (int)(temp[j] - '0');
else
arr[i][j] = -1;
}
}
int ret = dfs(0,0);
if (cycle) {
cout << -1;
return 0;
}
cout << ret;
return 0;
}풀이 흐름
-
dp배열을-1로 초기화합니다. -
보드를 입력받으면서 숫자는 정수로 변환하고 구멍
H는-1로 저장합니다. -
(0, 0)부터 DFS를 시작합니다. -
현재 위치가 보드 밖이거나 구멍이라면 더 이상 이동할 수 없으므로
0을 반환합니다. -
현재 위치가 이미
visited상태라면 현재 DFS 경로에서 같은 위치를 다시 만난 것이므로 사이클이 발생한 것입니다. -
이미
dp값이 계산된 위치라면 추가 탐색 없이 저장된 값을 반환합니다. -
처음 방문한 위치라면
visited[y][x] = 1로 설정합니다. -
현재 숫자만큼 상하좌우로 이동하며 각각 DFS를 수행합니다.
-
네 방향 중 가장 오래 움직일 수 있는 횟수를
dp[y][x]에 저장합니다. -
현재 위치의 탐색이 끝나면
visited[y][x] = 0으로 되돌립니다. -
DFS 전체 과정에서 사이클이 발견되었다면
-1, 그렇지 않다면dfs(0, 0)의 결과를 출력합니다.
구현 포인트
1. 구멍을 -1로 저장
if (temp[j] != 'H')
arr[i][j] = (int)(temp[j] - '0');
else
arr[i][j] = -1;입력은 문자열로 들어옵니다.
숫자인 경우
temp[j] - '0'을 통해 실제 정수 값으로 변환합니다.
구멍 H는 이동할 수 없는 위치이므로 -1로 저장하였습니다.
따라서 DFS에서
arr[y][x] == -1만 확인하면 구멍인지 쉽게 판단할 수 있습니다.
2. 게임이 종료되는 조건
if (y >= N || x >= M || y < 0 || x < 0 || arr[y][x] == -1) {
return 0;
}현재 위치가 보드 밖이거나 구멍이라면 게임이 종료됩니다.
이 위치에서는 추가로 움직일 수 없으므로 0을 반환합니다.
중요한 점은 현재 위치에서 보드 밖이나 구멍으로 이동하는 것 자체는 한 번의 이동으로 계산된다는 것입니다.
이를 부모 호출에서
1 + dfs(ny,nx)로 처리합니다.
예를 들어 다음 위치가 보드 밖이라면
dfs(보드 밖) = 0이고 부모에서는
1 + 0 = 1이 되므로 마지막 이동까지 정상적으로 횟수에 포함됩니다.
3. 현재 숫자만큼 이동
int ny = y + dy[i] * arr[y][x];
int nx = x + dx[i] * arr[y][x];현재 위치의 숫자가 X라면 한 칸씩 움직이는 것이 아니라 선택한 방향으로 정확히 X칸 이동해야 합니다.
방향 배열은
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};로 구성되어 있으므로 각각 상, 하, 우, 좌 방향을 나타냅니다.
현재 숫자를 방향 벡터에 곱하면 한 번에 정확한 다음 위치를 계산할 수 있습니다.
4. 중간에 있는 구멍은 확인하지 않음
문제에서는 이동하는 도중에 있는 구멍은 무시한다고 했습니다.
따라서 현재 위치에서 목적지까지 한 칸씩 확인할 필요가 없습니다.
int ny = y + dy[i] * arr[y][x];
int nx = x + dx[i] * arr[y][x];처럼 도착 위치만 계산하고, 해당 위치가 구멍인지 또는 보드 밖인지만 DFS에서 확인하면 됩니다.
5. dp의 의미
int dp[50][50];dp[y][x]는
(y, x)에서 시작했을 때 최대로 움직일 수 있는 횟수를 의미합니다.
처음에는 아직 계산되지 않았다는 의미로 모두 -1로 초기화합니다.
memset(dp, -1, sizeof(dp));6. 이미 계산한 위치는 다시 계산하지 않음
if (dp[y][x] != -1) {
return dp[y][x];
}DFS를 진행하다 보면 서로 다른 경로를 통해 같은 칸에 도착할 수 있습니다.
이때 해당 위치에서 시작했을 때의 최대 이동 횟수를 이미 계산했다면 똑같은 네 방향을 다시 탐색할 필요가 없습니다.
따라서 저장되어 있는 dp[y][x]를 바로 반환합니다.
이러한 방식으로 DFS의 중복 계산을 줄입니다.
7. 현재 위치의 최대 이동 횟수 계산
dp[y][x] = 0;현재 위치에서 네 방향을 확인하면서
dp[y][x] = max(dp[y][x], 1 + dfs(ny,nx));로 최대 이동 횟수를 갱신합니다.
dfs(ny, nx)는 다음 위치에서 추가로 움직일 수 있는 최대 횟수이고, 현재 위치에서 다음 위치로 이동하는 것까지 포함해야 하므로 1을 더합니다.
결국 네 방향 중 가장 오래 게임을 이어갈 수 있는 값을 선택합니다.
8. visited의 의미
int visited[50][50];이 문제에서 visited는 단순히
이 칸을 이전에 방문한 적이 있는가?를 의미하지 않습니다.
정확하게는
현재 DFS 경로에서 이 칸을 방문 중인가?를 나타냅니다.
이 차이가 사이클을 판단할 때 중요합니다.
9. 사이클 판단
if (visited[y][x]) {
cycle = true;
return 0;
}현재 DFS 경로에서 이미 방문 중인 위치를 다시 만났다는 것은 경로가 다시 이전 위치로 돌아왔다는 뜻입니다.
예를 들어 이동 관계가
A → B → C → A가 된다면 A를 다시 방문했을 때 visited[A] == 1입니다.
이 경우
A → B → C → A → B → C → ...처럼 같은 이동을 무한히 반복할 수 있습니다.
따라서 문제의 정답은 -1이 됩니다.
10. visited를 다시 0으로 만드는 이유
visited[y][x] = 1;로 현재 위치를 방문 중이라고 표시한 뒤 모든 탐색이 끝나면
visited[y][x] = 0;으로 되돌립니다.
visited는 전체 탐색에서 한 번이라도 방문했는지를 나타내는 배열이 아니라 현재 재귀 호출 경로를 나타내기 때문입니다.
예를 들어
A → B → D
A → C → D처럼 서로 다른 경로에서 D를 방문하는 것은 사이클이 아닙니다.
첫 번째 경로의 탐색이 끝난 후에도 visited[D]를 유지한다면 두 번째 경로에서 D를 방문했을 때 잘못 사이클이라고 판단하게 됩니다.
따라서 DFS에서 빠져나올 때 방문 표시를 제거합니다.
11. visited와 dp의 역할 차이
이 문제에서는 visited와 dp가 서로 다른 역할을 합니다.
visited : 현재 DFS 경로에서 방문 중인지 확인
dp : 이미 계산이 끝난 위치의 결과를 저장visited는 사이클 탐지를 위해 사용하고, dp는 중복 계산을 방지하기 위해 사용합니다.
즉,
visited → 사이클 탐지
dp → 메모이제이션으로 구분할 수 있습니다.
12. visited 검사를 dp보다 먼저 하는 이유
DFS에서는 다음 순서로 검사합니다.
if (visited[y][x]) {
cycle = true;
return 0;
}
if (dp[y][x] != -1) {
return dp[y][x];
}현재 재귀 경로에서 방문 중인 칸을 다시 만났다면 사이클 여부를 먼저 판단해야 합니다.
현재 탐색 중인 노드는
dp[y][x] = 0;으로 값이 이미 -1이 아닌 상태가 될 수 있기 때문입니다.
따라서 dp를 먼저 검사해버리면 현재 DFS 경로에서 다시 만난 노드를 단순히 계산 완료된 노드처럼 처리할 수 있습니다.
사이클 여부를 먼저 확인한 뒤, 사이클이 아니라면 기존에 계산된 dp 값을 사용하는 순서가 중요합니다.
13. cycle을 전역 flag로 관리
bool cycle;사이클은 하나라도 발견되면 게임을 무한히 진행할 수 있다는 의미입니다.
따라서 DFS 전체에서 공유할 수 있도록 cycle을 전역 변수로 두었습니다.
if (visited[y][x]) {
cycle = true;
return 0;
}탐색 과정에서 사이클이 한 번이라도 발견되면 true가 유지됩니다.
DFS가 종료된 후
if (cycle) {
cout << -1;
return 0;
}을 통해 최종 결과를 결정합니다.
14. 전체 로직 정리
이 문제에서는 DFS + DP + 사이클 탐지를 함께 사용하는 것이 핵심입니다.
전체적인 흐름은 다음과 같습니다.
(0, 0)에서 DFS 시작
↓
보드 밖 또는 구멍이면 0 반환
↓
현재 DFS 경로에서 방문 중?
↓ YES
사이클 발생 → cycle = true
↓ NO
이미 계산된 dp가 존재?
↓ YES
dp 값 바로 반환
↓ NO
현재 위치를 visited 처리
↓
상하좌우로 현재 숫자만큼 이동
↓
1 + dfs(다음 위치)의 최댓값 계산
↓
visited 해제
↓
dp 값 반환사이클이 존재하지 않는 경우 dp[0][0]이 최대 이동 횟수가 되고, 사이클이 하나라도 발견되었다면 -1을 출력합니다.
시간복잡도
사이클이 없는 경우 각 칸의 dp 값은 한 번 계산되면 이후 다시 계산하지 않습니다.
각 칸에서는 최대 네 방향을 확인하므로 보드의 크기를 N × M이라고 했을 때 시간복잡도는
O(N × M)입니다.
N, M이 각각 최대 50이므로 최대 2,500개의 칸을 확인하면 됩니다.
arr, visited, dp 배열 역시 보드 크기만큼 사용하므로 공간복잡도는
O(N × M)입니다.
