[PS] 백준 #14496. 그대, 그머가 되어

문제 정보

• 난이도: 실버 I
• 문제 주소: https://www.acmicpc.net/problem/14496
• 이 문제를 푼 이유: 그룹 연습 Div.2

 

문제

선린에 합격한 대호에게는 큰 고민이 있다. 대호는 중학교 3년 내내 공부만 했기 때문에, 요즘 학생들이 사용하는 ‘야민정음’에 대해서는 문외한이다. 친구들의 대화에 끼고 싶은 대호는 야민정음을 공부하기로 했다.

야민정음이란, 비슷한 모양의 글자를 원래 문자 대신에 사용하는 것을 일컫는다. 예를 들어, ‘그대’는 ‘그머’로, ‘팔도비빔면’은 ‘괄도네넴댼’으로, ‘식용유’는 ‘식용윾’으로, ‘대호’는 ‘머호’로 바꿀 수 있다. 아무 문자나 치환할 수 있는 건 아니며 치환이 가능한 몇 개의 문자들이 정해져있다.

예를 들어보자. (a, b), (a, c), (b, d), (c, d)가 주어지는 경우, a를 d로 바꾸는 방법은 a-b-d, a-c-d로 2개가 있다. (a, b), (b, c), (a, c)가 주어지는 경우, a를 c로 바꾸는 방법은 a-b-c, a-c의 2개가 있다. 하지만 이 경우에는 치환횟수에 차이가 생기게 된다.

머호는 문자 a를 문자 b로 바꾸려하고, N개의 문자와 치환 가능한 문자쌍 M개가 있다. 머호에게 a를 b로 바꾸기 위한 치환의 최소 횟수를 구해서 머호에게 알려주자!

프로그램 작성의 편의를 위해, 머호가 공부하는 모든 문자는 자연수로 표현되어 주어진다.

 

나의 풀이

단순한 BFS 문제다. 이 문제에서도 생각보다 시간을 많이 쏟았는데 요즘 코딩에서 손을 좀 놓아서 감이 떨어진 것이 원인인 것 같다. 문제 이해도 잘못해서 무향 그래프를 사용해야 되는데 유향 그래프에서 백 엣지를 이용하여 추적하는 방법만 계속 생각했다. cnt를 계산하는 위치도 잘못됐었다. 큐가 초기화될때까지 노드들을 꺼낸 후 cnt를 증가시켰어야 했는데, 노드 하나를 꺼낼때마다 cnt를 계산해서 틀리기도 했다. 노드의 개수가 적다보니 이 실수가 잘 드러나지 않았다. 

따라서 [무향 그래프 + BFS + 한 레벨에서 모두 방문이 끝나면 cnt 증가] 세 가지만 잘 캐치했으면 쉽게 풀리는 문제였다.

#include <bits/stdc++.h>

using namespace std;

// 1차 시도: 7% 틀렸습니다
// 2차 시도: 57% 메모리 초과
// 3차 시도: 57% 틀렸습니다
// 4차 시도: 92% 시간 초과

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// BFS 거리 구하기
	int a, b, n, m; cin >> a >> b >> n >> m;

	// n: 정점, m: 엣지 개수로 그래프 생성
	vector<vector<int>> graph;
	vector<bool> visited;

	graph.resize(n + 1);
	visited.resize(n + 1, false);

	for (int i = 0; i < m; i++) {
		int u, v; cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// BFS 과정
	int cnt = 0, curr;
	queue<int> qu, nextQu;
	qu.push(a);
	visited[a] = true;
	
	while (!qu.empty()) {
		int qsize = qu.size();
		for (int i = 0; i < qsize; i++) {
			curr = qu.front();
			qu.pop();
			if (curr == b) {
				cout << cnt; return 0;
			}
			for (int next : graph[curr]) {
				if (!visited[next]) {
					qu.push(next);
					visited[next] = true;
				}
			}
		}
		cnt++;
	}
	
	cout << -1;
}