백준 15723번 n단 논법

문제 링크입니다: https://www.acmicpc.net/problem/15723

플로이드 알고리즘을 이용해 푸는 그래프 문제였습니다.

플로이드 알고리즘을 생각하는 것은 어렵지 않은 문제였지만 굳이 입력을 'a is b' 이런식으로 받는 문제였기 때문에 고생했던 문제였습니다.

사실, scanf를 통해 문자열을 입력받으면 바로 해결되는 문제였지만 c++ 문법을 고집하다가 30분 정도 검색을 했던 것 같습니다.

결론은, n과 m을 입력받은 다음에 cin.ignore()를 진행해야 버퍼에 아무것도 남지 않아 getline에서 에러가 발생하지 않습니다.

#include <iostream>

#include <string>

using namespace std;

 

const int INF = 987654321;

const int MAX = 26;

 

int n, m;

int graph[MAX][MAX];

 

void initialize(void)

{

        for (int i = 0; i < MAX; i++)

                 for (int j = 0; j < MAX;j++)

                         if (i == j)

                                 graph[i][j] = 0;

                         else

                                 graph[i][j] = INF;

}

 

void floyd(void) //전형적인 floyd 알고리즘

{

        //i에서 k를 거쳐 j를 갈 수 있다 = 3단 논법

        for (int k = 0; k < MAX; k++)

                 for (int i = 0; i < MAX; i++)

                         for (int j = 0; j < MAX; j++)

                                 if (graph[i][j] > graph[i][k] + graph[k][j])

                                          graph[i][j] = graph[i][k] + graph[k][j];

}

 

int main(void)

{

        cin >> n;

        cin.ignore(); //추가 안할 경우 getline에서 subscript range 에러 발생

        initialize();

 

        for (int i = 0; i < n; i++)

        {

                 string hypothesis;

                 getline(cin, hypothesis); //그냥 cin으로 받을 경우 띄어쓰기 할 때마다 다른 문자열로 간주

                 graph[hypothesis[0] - 'a'][hypothesis[hypothesis.size() - 1] - 'a'] = 1; //간선 추가

        }

 

        floyd();

 

        cin >> m;

        cin.ignore();

 

        for (int i = 0; i < m; i++)

        {

                 string theorem;

                 getline(cin, theorem);

                

                 if (graph[theorem[0] - 'a'][theorem[theorem.size() - 1] - 'a'] != INF)

                         cout << "T" << endl;

                 else

                         cout << "F" << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~