백준 알고리즘 기초 - 그래프1 (연습)

연습치고는 너무 어려워..

2문제 밖에 없는 파트였다. 근데 엄청 헤맸다. 어려웠다.

뭔가 dfs, bfs 문제는 어느정도 감을 잡았다고 생각했는데 진짜 바보 같은 생각이었다 ㅋㅋ

2문제를 잘근잘근 씹어서 내껄로 한번 만들어 봐야겠다.

정리 시작!

-

* Two Dots (mid) : 사이클이 있는지 판별하는 문제다.

16929번: Two Dots

 - 여기서 말하는 사이클은 4개 이상의 서로 다르고 인접한 점의 집합을 말한다. 당연히 색은 다 같아야 한다.

 - 사이클을 판별하기 위해서 배열 d[i][j]를 선언해 인접한 점의 개수 합 cnt를 기록한다. 다음 조건엔 +1씩 해나간다. 

 - 그러다가 방문 여부를 기록하는 check[x][y]가 0이 아닐 때, 그러니까 이미 방문한 점을 방문했을 때, 현재 cnt 값에 d[x][y] 를 뺀 값이 4 이상이면 사이클이 존재한다. 개수가 4보다 크거나 같은, 변을 공유하는 점의 집합이 존재한다는 것을 알 수 있기 때문이다.

 - 아래와 같은 코드로 표현 가능하다.

#include <iostream>

using namespace std;

int n, m;
char a[50][50];
int d[50][50];
bool check[50][50];

int mx[] = { 0, 0, 1, -1 };
int my[] = { 1, -1, 0, 0 };

bool go(int x, int y, int cnt, char color) {
	if (check[x][y]) return cnt - d[x][y] >= 4;
	check[x][y] = true; d[x][y] = cnt;
	for (int i = 0; i < 4; i++) {
		int tx = x + mx[i];
		int ty = y + my[i];
		if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
			if (color == a[tx][ty]) {
				if (go(tx, ty, cnt + 1, color)) return true;
			}
		}
	}
	return false;
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (check[i][j] == 0) {
				if (go(i, j, 1, a[i][j])) {
					cout << "Yes" << '\n';
					return 0;
				}
			}
		}
	}

	cout << "No" << '\n';
	return 0;
}

 - 해당 경우의 점의 개수를 기록하는 배열을 따로 선언해서 기록하는 것, 사이클을 판별하는 조건을 생각하는 것이 관건이었다. 

 - 하지만 사이클의 존재 여부만 판단하기에 한계는 있다. 다음 문제에서 사이클에 포함된 점까지 구해보자.

 

* 서울 지하철 2호선 (hard) : 정답 코드를 봐도 이해가 안 됐다. 겨우 이해하고 안 까먹게 꼼꼼하게 정리 해본다.

16947번: 서울 지하철 2호선

 - 각각의 역과 순환선 사이의 거리를 구하는 문제다. 일단 순환선을 먼저 구하고, 그 다음 순환선에서의 거리를 구하면 된다. 순환선에 있는 역은 따로 거리를 안 구해도 될 거고, 순환선에 포함되지 않는 지선만 따로 카운트 해주면 된다.

 - 일단 순환선을 구하는 것부터 난관이었다. 아까 문제로 사이클이 있는지 없는지는 판별이 가능했는데, 이젠 구체적으로 어디가 사이클인지까지 알아내야 했다.

 - 음.. 처음엔 정답을 확인했는데도 이해를 못 했다. 한참을 보고 이해할 수 있었다. 주석으로 정리해봤다.

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

int n;
vector<int> a[3000];
int check[3000], dist[3000];

int mx[] = { 0, 0, 1, -1 };
int my[] = { 1, -1, 0, 0 };

int go(int x, int p) { // x가 현재 역, p가 이전 역이다. 처음 역의 이전 역은 -1로 처리한다. 
	// -2 : 사이클 찾음, 포함 x
	// -1 : 사이클 못 찾음
	// 0 ~ n-1 : 사이클 찾음, 시작 인덱스
	if (check[x] == 1) return x; // 이미 방문했던 곳에 방문. 여기가 시작 인덱스!
	check[x] = 1; // 방문 기록
	for (int y : a[x]) { // y는 x에 연결된 역
		if (y == p) continue; // 이미 지나온 역은 건너뛴다
		int res = go(y, x); // 사이클을 찾았으면 시작 인덱스가 담길 것
		if (res == -2) return -2; // 사이클을 찾았지만 순환선에 포함되지 않는 역
		if (res >= 0) { // 사이클을 찾은 경우
			check[x] = 2; // 사이클에 포함된 역
			if (x == res) return -2; // 사이클이 끝난 것이므로 그 다음부터는 -2를 리턴
            else return res;		 // 다르면 순환선이 덜 끝난 것이므로 res 리턴
		}
	}
	return -1; // 사이클을 찾지 못한 경우
}

int main()
{
	cin >> n;
	int x, y;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		x -= 1; y -= 1; // 계산 편의를 위해 -1 해서 저장
		a[x].push_back(y);
		a[y].push_back(x);
	}

	go(0, -1);

	queue <int> q;
	for (int i = 0; i < n; i++) {
		if (check[i] == 2) {
			dist[i] = 0;
			q.push(i);
		}
		else {
			dist[i] = -1;
		}
	}

	while (!q.empty()) {
		int tx = q.front();
		q.pop();
		for (int y : a[tx]) {
			if (dist[y] == -1) {
				dist[y] = dist[tx] + 1;
				q.push(y);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		cout << dist[i] << ' ';
	}
	cout << '\n';

	return 0;
}

- 이 정도면 나중에 봐도 이해할 수 있겠지? 연습이 이 정도인데 도전은 어떨까.. 와~~설렌다~~~ 하...

-

문제가 안 풀릴 수록 뭔가 스트레스가 쌓이는 느낌인데.. 전혀 그럴 필요가 없다.

충분히 고민하고도 풀리지 않으면 못 푸는 거다. 낑낑대서 풀어봤자 코드도 어거지로 나온다.

정석 코드를 보고 이해하는 것도 공부 방법 중 하나다. 너무 직접 풀려고 하다가 시간을 낭비하지 말자.

이제 그래프도 마지막 파트다. 꾸준히 화이팅 해보자.

정리 끝!