SW Expert 1227. [S/W 문제해결 기본] 7일차 - 미로2 (D4)

문제 출처 : SW Expert

SW Expert Academy

Q. 출발지와 도착지가 주어졌을 때, 출발지 부터 도착지 까지 경로가 있는 지 판단하는 프로그램을 작성하시오.

단, 지도는 100X100 행렬 형태이며, 출발지는 2, 도착지는 3, 경로는 0, 벽은 1로 표현된다.

 

전형적인 완전탐색 문제에요. 탐색을 진행하다 도착지에 도달하면 탐색을 끝내는 방향으로 문제를 해결했습니다.

bfs로도 해결할 수 있지만 저는 dfs로 해결했습니다.

너무 기본적인 해결방법이라 더 이상의 설명보다 코드를 보여드리는게 나을 꺼 같습니다. 헤헤

 

#include<iostream>
#include<cstring>
#include<string>
 
using namespace std;
 
int map[102][102];
int check[102][102];
 
int dir_x[4] = { 0,1,0,-1 };
int dir_y[4] = { 1,0,-1,0 };
 
int result = 0;
 
void dfs(int x, int y) {
    int chance = 0;
    check[y][x] = 1; // 중복 탐색 방지
    for (int i = 0; i < 4; i++) {
 
        int next_x = x + dir_x[i];
        int next_y = y + dir_y[i];
 
        if (map[next_y][next_x] == 3) {
            result = 1;
        }
        else if (map[next_y][next_x] == 0 && check[next_y][next_x] == 0 && result == 0) { // result를 검사, 도착지에 방문하면 탐색 종료
            
            dfs(next_x, next_y);
        }
    }
}
int main() {
    int T = 10;
    int idx = 0;
 
    while (idx++ < T) {
        int n;
 
        cin >> n;
 
        memset(map, -1, sizeof(map));
 
        string s;
 
        int start_x = 0;
        int start_y = 0;
 
        for (int i = 1; i < 101; i++) {
            cin >> s;
 
            for (int j = 1; j < 101; j++) {
                map[i][j] = s[j - 1] - '0';
                
                if (map[i][j] == 2) {
                    start_y = i;
                    start_x = j;
                }
            }
        }
    
        dfs(start_x, start_y);
 
        if (result == 1)
            cout << "#" << idx << " 1" << endl;
        else 
            cout << "#" << idx << " 0" << endl;
 
        result = 0;
        memset(check, 0, sizeof(check));
    }
}

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!