[C++] SWEA 1219 - 길찾기(2)

두 번째 풀이입니다. 예전과는 어떻게 얼마나 달라졌는지 궁금해서 한번 더 풀어보았습니다.

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

SW Expert Academy

<풀이>

1. 길 정보가 주어진다.

2. 출발점(0)에서 도착점(99)로 갈 수 있는지 출력한다.

 

<해법>

1. 알고리즘 선택하기

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

 

#include <iostream>
#include <string.h>
 
using namespace std;
 
int trash;
int cnt;
int map[100][2];
bool visited[100];
bool answer;
 
bool canGo(int node) {
    if (node == 99) return true;
 
    bool ret = false;
    visited[node] = true;
    for (int i = 0; i < 2; i++) {
        int nxt = map[node][i];
        if (nxt != -1 && !visited[nxt]) {
            ret |= canGo(nxt);
        }
    }
    return ret;
}
 
void solution() {
    answer = canGo(0);
}
 
int main() {
    int test_case;
    int T;
 
    T = 10;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        trash = 0;
        cnt = 0;
        memset(map, -1, sizeof(map));
        memset(visited, false, sizeof(visited));
        answer = false;
 
        //입력
        cin >> trash >> cnt;
        for (int i = 0; i < cnt; i++) {
            int from = 0, to = 0;
            cin >> from >> to;
            if (map[from][0] == -1) map[from][0] = to;
            else map[from][1] = to;
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

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