[SWEA_D4] 1226번 - 미로 1

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE&&&

SW Expert Academy

dfs 알고리즘을 활용한 완전탐색 문제다.

주어진 조건대로 0이거나 목적지인 3인 경우만 갈 수 있게 설정하고, 방문하지 않은 곳에 대해서만 방문하도록 했다.

문자 -> 숫자 변환은 '0'을 빼는 것이므로 47번째 줄에서 처리해주었다.

 

아래는 코드

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
vector<vector<int> > MAP;
vector<vector<bool> > check;
int r_s, c_s;
int answer = 0;
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
void dfs(int r, int c){
    if (MAP[r][c] == 3){
        answer = 1;
        return;
    }
    check[r][c] = true;
    for (int i = 0; i < 4; i++){
        int nr = r + direction[i].dr;
        int nc = c + direction[i].dc;
        if (nr >= 0 && nr < 16 && nc >= 0 && nc < 16){
            if ((MAP[nr][nc] == 0 || MAP[nr][nc] == 3) && !check[nr][nc]){
                dfs(nr, nc);
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    for (int tc = 1; tc <= 10; tc++){
        int t;
        cin >> t;
        answer = 0;
        MAP.assign(16, vector<int>(16, 0));
        check.assign(16, vector<bool>(16, false));
        for (int r = 0; r < 16; r++){
            string curRow;
            cin >> curRow;
            for (int c = 0; c < 16; c++){
                MAP[r][c] = curRow[c] - '0';
                if (MAP[r][c] == 2){
                    r_s = r;
                    c_s = c;
                }
            }
        }
        dfs(r_s, c_s);
        cout << "#" << t << " " << answer << '\n';
    }
    return 0;
}