[C++] SWEA 1219 - 길찾기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14geLqABQCFAYD

SW Expert Academy

<풀이>

1. 두 도시를 연결하는 도로 입력값들로 배열을 만든다.

2. 맵을 탐색하며 도착점에 갈 수 있는지 판단하여 출력한다.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
int map[2][100];
bool visited[100];
int START = 0, END = 99;
 
int bfs(int st) {
    queue<int> q;
    q.push(st);
    visited[st] = true;
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        //현재 도시가 도착점일 경우 1 반환
        if (cur == END) {
            return 1;
        }
 
        //현재 도시와 연결되어있는 다음 도시 큐에 담기
        for (int i = 0; i < 2; i++) {
            int nxt = map[i][cur];
            if (nxt >= 0 && !visited[nxt]) {
                q.push(nxt);
                visited[nxt] = true;
            }
        }
    }
 
    //도착점에 방문한 적이 없는 경우 0 반환
    return 0;
}
 
int main() {
    
    int test_case;
    int T;
 
    T = 10;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //케이스마다 사용할 전역변수 초기화
        memset(map, -1, sizeof(map));
        memset(visited, false, sizeof(visited));
 
        //입력
        int case_num, road_cnt;
        cin >> case_num >> road_cnt;
 
        for (int i = 0; i < road_cnt; i++) {
            int a, b;
            cin >> a >> b;
 
            //연결되어 있는 길 저장
            if (map[0][a] < 0) {
                map[0][a] = b;
            }
            else {
                map[1][a] = b;
            }
        }
 
        //탐색
        int res = bfs(START);
 
        //출력
        cout << "#" << case_num << " " << res << "\n";
    }
}

 

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