[백준] 9944번 NM보드 완주하기

9944번 N*M 보드 완주하기

문제) https://www.acmicpc.net/problem/9944

풀이)

처음에 구조체 ball을 하나 만들어서, bfs로 구현 시도해보았는데 다시 방문한 곳을 방문처리하기가 까다로웠다.

처음 시도 방법)

struct ball {

int y, x, dir, cnt, change;

ball() {}

ball(int y,int x, int dir) {

this->y = y; //y좌표

this->x = x; //x좌표

this->dir = dir; //공이 움직이는 방향

this->cnt = 1; //공이 방문한 빈칸 개수

this->change = 1; //공이 방향을 바꾼 횟수

}

};

bool visited[y][x][dir 0 ~ 4]

2번째 시도 방법)

방문처리를 back tracking 방식으로 초기화 해주는 방법을 사용했다.

그래서 구조체를 사용하지 않고 그냥 dfs만 이용해서 풀었다.

과정

1. 맵상의 모든 빈칸을 공이 시작할 수 있는 위치로 본다.

2. 처음의 공은 상하좌우 모든 방향으로 이동 시작이 가능하다.

3. 공을 이동시킨다.

 3.1 공이 벽을 만나거나, 경계를 만나거나 이전에 방문했던 공이면 방향을 바꿔 공을 다시 이동시킨다.

 3.2 공이 방문한 칸의 횟수가 전체 맵상의 빈칸 수와 같다면 공을 이동시킨 최소 횟수를 갱신한다.

주의할 점

1. 공이 움직일 수 있는 칸이 없다면, 이동 횟수는 0이다.

   ex)

****

**.*

****

****

2. 종료조건이 주어지지 않아서 입력값이 없으면 종료되게 만들어 줘야한다.

 참고)

    콘솔에서 직접 입력을 넣을 땐 EOF를 수동으로 넣어줘야한다.

    윈도우 기준으로는 Ctrl + Z, UNIX 기준으로는 Ctrl + D.

     BOJ에서는 입력을 넣을 때 파일로 주기 때문에 EOF가 붙어 있다.

    EOF == -1

코드)

#include <stdio.h>
#include <queue>
#include <iostream>
#include<string.h>
using namespace std;
 
#define MAX 999999999
int n, m;
char map[31][31];
bool visited[31][31];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int empty_count;
int result = MAX;
 
bool IsNotok(int y, int x) {
    if (y < 0 || y >= n || x < 0 || x >= m || map[y][x] == '*' || visited[y][x]) return true;
    return false;
}
 
void dfs(int y, int x, int dir, int cnt, int change) {
 
    if (cnt == empty_count) {
        result = result > change ? change : result;
        return;
    }
 
    int ny = y + dy[dir];
    int nx = x + dx[dir];
 
    if (IsNotok(ny,nx)) {//새로운 위치가 벽, 경계 넘음, 이미 방문했던 곳 이라면 방문하지 못함.
        for (int i = 0; i < 4; i++) {
            if (i == dir)continue;
            ny = y + dy[i];//방향을 바꾼 새로운 이동 칸
            nx = x + dx[i];
 
            if (!IsNotok(ny, nx)) { //방향을 바꾼 새로운 이동 칸 위치가 방문할 수 있는 곳이라면
                visited[ny][nx] = true;
                dfs(ny, nx, i, cnt + 1, change + 1);
                visited[ny][nx] = false;
            }
        }
    }
    else {
        visited[ny][nx] = true;
        dfs(ny, nx, dir, cnt + 1, change);
        visited[ny][nx] = false;
    }
}
 
int main() {
    int test_case = 1;
    while (cin >> n >> m)
    {
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> map[i][j];
                if (map[i][j] == '.') empty_count++;
            }
        }
        if (empty_count == 0) {
            printf("Case %d: %d\n",test_case, 0);
        }
        else {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (map[i][j] == '.') {
                        visited[i][j] = true;
                        for (int d = 0; d < 4; d++) {
                            dfs(i, j, d, 1, 1);
                        }
                        visited[i][j] = false;
                    }
                }
            }
            printf("Case %d: %d\n",test_case, result == MAX? -1 : result);
        } 
        test_case++;
        memset(visited, 0, sizeof(visited));
        memset(map, 0, sizeof(map));
        result = MAX;
        empty_count = 0;
    }
    
    return 0;
}