ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1226.미로1 & 1227.미로2
    알고리즘/SW Expert Academy 2020. 3. 26. 00:16

    이번문제는 미로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구현하기를 해보자.

    '알고리즘 > SW Expert Academy' 카테고리의 다른 글

    1229.암호문2  (0) 2020.03.31
    1228.암호문1  (0) 2020.03.29
    1226.미로1 & 1227.미로2  (0) 2020.03.26
    1225. 암호생성기  (0) 2020.03.24
    1224.계산기3  (0) 2020.03.24
    1223.계산기2  (0) 2020.03.23

    댓글 0

Designed by Tistory.