BOJ 1976 여행가자

www.acmicpc.net/problem/1976

1976번: 여행 가자

여행을 가고 싶어서 풀기 시작해서 화난 문제이다.

와 진짜 상상도 못한 곳에서 어이가 없어진 문제였다. 아이디어는 다음과 같다. BFS나 DFS를 사용할 수 있다면 편하게 풀 수 있는 문제.

Destination을 따로 받는다. 그렇게 된다면 1 2 4 5 이런 식으로 될텐데 destination[1]부터 bfs를 돌려서 destination[i-1]에서 시작해 destination[i]에 도착하면 그냥 true를 리턴해주거나 아니면 그걸 배열에 저장해준 다음 한꺼번에 체크하며 출력하면 되는 문젠데, 예상치도 못한 부분에서 틀렸다. 그래서 뭔지 아무리 고민해도 모르겠길래 질문을 검색했더니 이런 댓글이 있었다.

 

3

3

0 0 0

0 0 0

0 0 0

1 1

 

그래, 상식적으로 생각하면 이거 되는 문제다. 왜냐? 내가 서울에 사는데 서울에 갈 수 있다는 무조건 참이니까 말이다.

하지만 그래프에서는 당연히 불가능하다. 당연하지 않은가? 움직일 수가 없는데 어떻게 가냐고. 그래서... 뭐 그거 추가하고 맞췄다. 좀 열받았다. 쉬운 문제였는데.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int M,N;
vector<vector<int>> Graph;
vector<bool> ans;
vector<int> destination;

void bfs(int start, int dest)
{
	queue<int> q;
	q.push(start);
	vector<bool> check(N+1);
	check[start] = true;
	if (start == dest) {
		ans.push_back(true);
		return;
	}
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = 0; i < Graph[x].size(); i++)
		{
			int y = Graph[x][i];
			if (y == dest) {
				ans.push_back(true);
				return;
			}
			if (!check[y])
			{
				q.push(y);
				check[y] = true;
				
			}
		}
	}
	ans.push_back(false);
	return;
}
int main() {
	ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	Graph = vector<vector<int>>(N+1);
	destination = vector<int>(M);
	for (int i = 1; i < N+1; i++) {
		for (int j = 1; j < N + 1; j++) {
			int tmp;
			cin >> tmp;
			if (tmp == 1) {
				Graph[i].push_back(j);
			}
		}	
	}
	for (int i = 0; i < M; i++) {
		cin >> destination[i];
		if (i > 0) {
			bfs(destination[i - 1], destination[i]);
		}
	}
	for (int i = 0; i < M - 1; i++) {
		if (!ans[i])
		{
			cout << "NO";
			return 0;
		}
	}
	cout << "YES";
	return 0;

}