1226.미로1 & 1227.미로2

이번문제는 미로1과 미로2이다.

문제는 간단하다. 주어진 출발지에서 주어진 목적지까지 갈 수 있나 없나를 체크하는

알고리즘을 구현하는 것이고 나는 DFS를 이용하기로 했다. 문제는 queue강의에서 출제되었지만

나는 DFS를 Stack을 이용해서 구현해보았다. 앞서 stack과 queue를 나름 많이 다뤄보아서인지

사용이 자연스러워진거같다. 처음 시작할 때는 분명 헷갈렸던 것 같은데.. ㅎㅎ

미로1과 미로2는 MAX를 16이나 100이냐 말고 코드가 달라진게 없어서 한 번에 포스팅했다.

 

< Code 설명 >

#include <iostream>
#include <stack>
#include <string.h>

using namespace std;

#define MAX 16 // 100


int dx[4]={-1,1,0,0}; // X축 이동
int dy[4]={0,0,-1,1}; // Y축 이동
int map[MAX][MAX];    // 맵
bool check[MAX][MAX]; // 방문여부
void init(){          // 10개의 테스트케이스 시 초기화해줘야하므로
    memset(check,false,sizeof(check));
    memset(map,0,sizeof(map));
}

int main()
{
    for(int k=0; k<10; k++){
        init();                   // 초기화진행
        int num;                  // 순서를 보여주기위해 입력받는 값
        bool done = false;        // 찾았는지 못찾았는지 알려주는 값
        cin >> num;   
        stack <pair<int,int>> s;  // 좌표를 한쌍으로 스택생성 
        for(int i=0; i<MAX; i++){ 
            for(int j=0; j<MAX; j++){
                scanf("%1d",&map[i][j]);    // Map 모양 저장
                if(map[i][j]==2)            // 출발지 값을 찾으면
                    s.push(make_pair(i,j)); // 바로 스택에 저장
            }
        }
        int x = s.top().first; // 스택의 최상위를 출발지 x좌표 저장
        int y = s.top().second;// 스택의 최상위를 출발지 y좌표 저장 
        while(!s.empty()){     // 스택이 빌 때 까지 탐색한다.
            for(int i=0; i<4; i++){  
                int ax=x+dx[i]; // x, y좌표에
                int ay=y+dy[i]; // 축이동 배열을 더해 상하좌우를 탐색하기 위함
                
                if(ax>0 || ay>0 || ax<MAX || ay<MAX){  // 지도를 벗어나지 않는조건
                    if(map[ax][ay]==0 && check[ax][ay]==false){ //길이있고 방문X
                        s.push(make_pair(ax,ay)); //그렇다면 스택에 저장
                        check[ax][ay]=true;       //해당좌표 방문 Check
                        x = s.top().first;        //방문한 부분부터 다시 상하좌우 
                        y = s.top().second;       //비교하기 위해 x,y좌표 설정
                        i=-1;                     //i=0부터 탐색해야하므로
                    }
                }
                if(map[ax][ay]==3){                    //목적지를 찾으면 
                    cout << "#" << num <<" 1" << endl; //1을 출력해주자
                    done = true;                       //찾았다는 변수 true!
                    break;                             //찾으면 끝이므로 그만!
                }
            }
            if(done==true)           // 찾으면 끝이니까 스택이 비고말고 할거없이 끝!
                break;
            if(!s.empty()){          // 만약 길이 막혔을 경우
                s.pop();             // 그 좌표에서는 더이상 갈 곳이 없으므로 pop!
                if(!s.empty()){      //그럼에도 스택이 남아있다면
                    x=s.top().first; // 그 최상위 스택 좌표에서 방문하지 않은 곳이 
                    y=s.top().second;// 있을 수 있기 때문에 좌표로 다시설정해서 탐색
                }
            }
        }
        if(done==false)                        // 만약 목적지를 못찾았다면 
            cout << "#" << num <<" 0" << endl; // 0을 출력!
    }
    return 0;
}

# Stack이 아닌 Queue를 이용해서도 구현해보아야겠다. 재귀함수도:)

# Stack으로 Queue구현하기 반대로 Queue로 Stack구현하기를 해보자.