[SWEA] 1226. [S/W 문제해결 기본] 7일차 - 미로1

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

SW Expert Academy

시작점을 큐에 넣고 bfs를 사용해서 도착점에 방문하는지 확인해주면 된다.

도착점을 확인하기 위해 입력받을 때 도착점의 좌표를 따로 저장해둔다.

 

bfs를 할 때 길인 경우(값이 0인 경우)에만 방문을 하게 해서 계속 답이 0이 나왔었다...ㅠㅠ

도착지점인 경우(값이 3인 경우)도 방문하도록 해줘야 한다!

 

결과적으로 도착지점에 방문을 했으면 1을 출력 못했으면 0을 출력하면 된다.

 

 

참고로 미로2 문제도 미로의 크기만 100으로 하면 똑같이 풀 수 있다.

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
 
int map[16][16];
bool check[16][16];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
 
 
int main() {
    int T = 10;
    int num;
 
 
    for(int tc=1; tc<=T; tc++) {
        scanf("%d",&num);
 
        int endX, endY;
        queue<pair<int,int> > q;
 
        for(int i=0; i<16; i++) {
            for(int j=0; j<16; j++) {
                scanf("%1d", &map[i][j]);
                check[i][j] = false;
 
                //시작점이면 큐에 삽입후 방문 체크
                if(map[i][j] == 2) {
                    q.push(make_pair(i,j));
                    check[i][j] = true;
                } else if(map[i][j] == 3) { //도착점의 좌표를 저장
                    endX = i;
                    endY = j;
                }
            }
        }
 
        while(!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            for(int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
 
                //범위 체크
                if(nx < 0 || ny < 0 || nx >= 100 || ny >= 100) continue;
 
                //길이고, 방문하지 않았으면 방문
                if(map[nx][ny] == 0 && check[nx][ny] == false) {
                    q.push(make_pair(nx,ny));
                    check[nx][ny] = true;
                } else if(map[nx][ny] == 3) {
                    //도착점인 경우 방문
                    q.push(make_pair(nx,ny));
                    check[nx][ny] = true;
                }
                 
            }
 
        }
 
        //도착점에 방문했으면 1을 출력
        if(check[endX][endY]) {
            printf("#%d %d\n",tc,1);
        } else { //도착점에 도착하지 못했으면 0을 출력
            printf("#%d %d\n",tc,0);
        }
 
 
    }
 
    return 0;
}