https://www.acmicpc.net/problem/1103
문제
> 형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.
> 일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.
> 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
> 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
> 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.
> 만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다.
> 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.
> 보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.접근
DFS를 이용해서 시작점에서 사방으로 DFS를 해나가며 바닥에 쓰인 숫자 만큼 4방으로 나아간다.
이때, 이동횟수를 누적하는데 밖으로 나가거나, 구멍에 빠지면 이동거리 +1 하고 끝내주고,
만약 방문했던 위치에 또 오면 해당 DFS에서 사이클이 생긴다는 뜻이므로 바로 -1출력하고 끝내준다.
이제 보드안에서 돌아다닐때, dp를 통해서 매 DFS의 가지마다 해당 위치의 이동횟수를 저장한다.
만약 다른 DFS에서 해당 위치에 왔는데 저장되어있는 dp값 보다 작거나 같으면 더 않좋은 경우니까 볼 필요가 없다. 따라서, 더 클 때만 dp값을 갱신하며 DFS를 나아간다.
문제해결
> N과 M을 입력받고 보드의 정보를 저장할 char형 벡터, 방문처리를할 visited벡터를 선언한다.
> 각 위치마다 최적의 횟수를 누적할 dp벡터를 선언하고 사방탐색을 위한 방향을 정의한다.
> 조건을 다 입력받고 보드를 만들어주고, 시작점 0,0에 방문처리를 해주고 DFS메서드를 호출한다.
> DFS 내부에선 기본적으로 사방탐색을 하는데 현 위치의 수를 go에 담아 몇칸 갈지 잡아준다.
> 이를 이용해 새 좌표를 잡고 범위 밖인지, 구멍인지 확인하는데 맞다면 지금까지의 거리 dist에 나가거나, 빠지는 횟수 +1 해서 최종 횟수인 rst에 max연산 해준다.
> 이제 갔던 곳인지 확인하는데 갔던 곳이라면 사이클이 생기므로 -1을 출력하고 바로끝낸다.
> 만약 방문한 곳이 아니면 방문처리 해주면서 재귀로 들어간다. 끝나고 나오면 방문처리를 되돌린다.
> 이제 dp작업을 해주는데 DFS로 현 좌표를 볼 때 처리한다.
> 현 위치의 dp값이 없으면 저장하고, 있는데 현재의 이동횟수가 저장된 이동횟수보다 작으면 더 안좋은 경우가 되므로 해당 DFS는 끝내준다.
> 이제 DFS로 모든 지점을 본 뒤, 모든 지점의 dp값중 최대값을 찾아 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
//1103 게임
int N, M;
vector<vector<char>> board;
vector<vector<bool>> visited;
vector<vector<int>> dp;
int dir[4] = { -1, 1, 0, 0 }, dic[4] = { 0, 0, -1, 1 };
int rst = 0;
void DFS(int sr, int sc, int dist) {
if (dp[sr][sc] >= dist) return;
dp[sr][sc] = dist;
int go = board[sr][sc] - '0';
for (int i = 0; i < 4; i++) {
int nr = sr + dir[i] * go;
int nc = sc + dic[i] * go;
if (nr >= N || nr < 0 || nc >= M || nc < 0 || board[nr][nc] == 'H') {
rst = max(rst, dist + 1);
continue;
}
if (visited[nr][nc]) {
cout << -1 << '\n';
return exit(0);
}
visited[nr][nc] = true;
DFS(nr, nc, dist + 1);
visited[nr][nc] = false;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
board.resize(N, vector<char>(M));
visited.assign(N, vector<bool>(M, false));
dp.assign(N, vector<int>(M, -1));
for (int i = 0; i < N; i++) {
string str;
cin >> str;
for (int j = 0; j < M; j++) board[i][j] = str[j];
}
visited[0][0] = true;
DFS(0, 0, 0);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) rst = max(rst, dp[i][j]);
}
cout << rst << '\n';
}
후기
흐름을 파악하고 이해하는데 어려웠다..dp가 섞여버리니까 헷갈리눈구나..
