1103: 게임

• toc {:toc}

문제 확인

1103: 게임 문제 확인하기

풀이

동전이 4방향으로 이동하면서 움직일 수 있는 최대의 경우의 수를 구하는 문제이다.

1. 입력이 space가 주어져서 들어오는 것이 아니라 한 번에 들어온다.
   • string으로 받을지 int로 받을지 선택. 둘 다 상관없긴 하다.
   • board에 나눈 숫자 저장
2. 최대의 경우의 수를 구하는 문제 ⇒ 모든 경우의 수를 파악해서 최대의 경우의 수 산출 (DFS)
   • 경우의 수 저장을 위해 dist 배열 생성해 이동 거리 저장
   • 원점으로부터 가능한 먼 곳으로 재귀적으로 이동하며 -1인 dist값을 0으로 초기화
   • 먼 곳에서부터 이동가능한 경우의 수를 세며 원점으로 돌아오는 방식
3. 고려해야 하는 예외 사항
   • 무한번 움직이는 경우 ⇒ vis 로 방문한 경우 1로 체크. 다시 방문하면 무한번 이동한다 가정
   • 동전이 구멍에 빠지거나 보드 바깥으로 나가는 경우

#include <bits/stdc++.h>
using namespace std;
 
int board[50][50];
int vis[50][50];
int dist[50][50];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int N, M;
 
int dfs(int x, int y){
    if (board[x][y] == 0 || x < 0 || x >= N || y < 0 || y >= M) return 0;
    if (vis[x][y] == 1) {
        cout << -1 << endl;
        exit(0);
    }
    if (dist[x][y] != -1) return dist[x][y];
 
    vis[x][y] = 1;
    dist[x][y] = 0;
 
    int mat = board[x][y];
    for(int dir = 0; dir<4; dir++){
        int nx = x + dx[dir] * mat;
        int ny = y + dy[dir] * mat;
        if(dist[x][y]<dfs(nx, ny)+1){
            dist[x][y] = dfs(nx, ny)+1;
        }
    }
    vis[x][y] = 0;
    return dist[x][y];
}
 
 
int main(){
    ios::sync_with_stdio(true);
    cin.tie(0); cout.tie(0);
 
    cin >> N >> M;
    for (int row=0; row<N; row++){
        string str;
        cin >> str;
        for (int col=0; col<M; col++){
            dist[row][col] = -1;
            int val;
            if (str[col]=='H') val = 0;
            else {
                val = int(str[col]) - 48;
            }
 
            board[row][col] = val;
        }
    }
 
    int res = dfs(0,0);
 
    cout << res << endl;
 
    return 0;
}