[C++] SWEA 1226 - 미로1

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE&problemTitle=1226&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

<풀이>

1. 미로를 입력받는다.

2. 미로 출발점부터 도착점까지 갈 수 있는지 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 길찾기 알고리즘으로 DFS(스택, 재귀함수), BFS(큐)가 있습니다. 모든 방법으로 풀이가 가능합니다(모든 방법으로 풀어보았습니다). 저는 DFS(재귀함수)를 이용한 코드를 올리겠습니다.

 

#include <iostream>
#include <string.h>
 
using namespace std;
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int trash;
char map[16][16];
bool visited[16][16];
int startX, startY, endX, endY;
bool answer;
 
bool isInner(int x, int y) {
    if (x < 0 || y < 0 || x >= 16 || y >= 16) return false;
    return true;
}
 
bool canExit(int x, int y) {
 
    if (x == endX && y == endY) return true;
 
    bool ret = false;
 
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (!isInner(nx, ny) || visited[nx][ny] || map[nx][ny] == '1') continue;
        
        ret |= canExit(nx, ny);
    }
    return ret;
}
 
void solution() {
    answer = canExit(startX, startY);
}
 
int main() {
    int test_case;
    int T;
 
    T = 10;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        trash = 0;
        memset(map, 0, sizeof(map));
        memset(visited, false, sizeof(visited));
        startX = 0, startY = 0, endX = 0, endY = 0;
        answer = false;
 
        //입력
        cin >> trash;
        for (int i = 0; i < 16; i++) {
            for (int j = 0; j < 16; j++) {
                cin >> map[i][j];
                if (map[i][j] == '2') {
                    startX = i, startY = j;
                }
                else if (map[i][j] == '3') {
                    endX = i, endY = j;
                }
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

DFS, BFS에 대해 알아볼 수 있는 문제였습니다.