(C++) - 백준(BOJ) 15723번 : n단 논법

https://www.acmicpc.net/problem/15723

15723번: n단 논법

bfs로 해결한 문제였습니다.

 

 

 

📕 풀이방법

📔 입력 및 초기화

 1. 삼단논법을 그래프로 빗대어 설명하자면 a에서 b로가는 길이 있고 b에서 c로가는 길이 있는 경우에 a에서 c로가는 길이 있음이 자명합니다. 

 

 2. 적절히 입력을 받아 유향 인접 그래프를 형성합니다.

 

 

📔 풀이과정

 1. m개의 질문에 대해 다음을 수행합니다.

 

  1-1. getline으로 한줄 입력받고 x,y 문자변수에 해당하는 질문 알파벳을 저장합니다.

 

  1-2. bfs를 수행해 x에서 출발해 y에 도착할 수 있는지 여부를 확인해 반환합니다.

 

📔 정답출력

bfs수행 반환값이 1이라면 성공적으로 도착했으므로 T, 0이라면 F를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, m, ck[26];
vector <int> graph[26];

int bfs(int start, int end){
    queue <int> q;
    q.push(start);
    ck[start] = 1;
    memset(ck,0,sizeof(ck));

    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(auto next : graph[x]){
            if(ck[next]) continue;
            ck[next] = 1;
            q.push(next);
        }
    }
    return ck[end];
}

int main(){
    cin >> n;
    cin.ignore();
    while(n--){
        char x,y;
        string s;
        getline(cin,s);
        x = s[0];
        y = s[s.size() - 1];
        graph[x-'a'].push_back(y-'a');
    }
    cin >> m;
    cin.ignore();
    while(m--){
        char x,y;
        string s;
        getline(cin,s);
        x = s[0];
        y = s[s.size() - 1];
        if(bfs(x-'a',y-'a')) cout << "T\n";
        else cout << "F\n";
    }
}