boj, 백준) 5022. 연결(C/C++)

1. 문제 링크

www.acmicpc.net/problem/5022

5022번: 연결

2. 문제 개요

전기 회로에서 두 점을 전선으로 이을 때, 길이는 짧을수록 좋다.

크기가 N x M인 비어있는 회로판에서 두 점 A1, A2, 그리고 B1, B2를 전선을 이용해서 이으려고 한다. 전선은 항상 그리드의 수직, 수평선 위에 있어야 한다. 또, 두 직선은 접하면 안 된다. 이 경우에 필요한 전선의 길이의 최솟값을 구하는 프로그램을 작성하시오. 전선은 회로판 바깥으로 나갈 수 없다.

 

3. 문제 힌트

(1) (A1--A2) (B1--B2) 둘다 최단거리로 연결된 경우

(2) A만 최단거리 B는 둘러가는경우,

(3) A는 둘러가고 B만 최단거리

(4) A, B둘다 동시에 연결할 수 없는 경우(impossible출력)

 

위의 4가지 중 최단거리는 존재한다.

 

(2)의 예를 들어서, A가 최단거리로 연결된다고 하면, B의 점들의 시작점은 가지 않게 하고, A의 최단거리를 구한다. 이때 경로를 기록하여 B를 연결하려고 할 때, A가 연결된 부분을 지나가지 않도록 처리해 주어야 한다.

4. 문제 풀이

처음 문제를 봤을 때, 3번 문제 힌트에 있는 조건들을 바로 생각했다. 하지만 여기서 A도 둘러가고 B도 둘러가서 최솟값을 만드는 경우는 없을까?라고 생각했다.

이게 없다는 것을 찾으면 이 문제의 정답은 항상 한 점(A1 ~ A2) 이상은 최단거리로 연결되어있어야 함을 의미하기 때문이다.

그래서 수식으로 없다는 걸 증명하기는 어려우니..  A도 둘러가고 B도 둘러가서 최단거리를 만드는 예제를 최대한 찾으려고 했다. 꼭 수식으로 증명하지 않아도 반례를 들면 증명이 되니.. (둘러가는 건 최단거리로 가지 않는 것을 의미합니다)

 

5~10분 정도 찾다가.. 아무리 생각해도 그런 예제는 없는 것 같아, 코딩을 끝내고 질문 검색란에 들어가서 글을 봤는데, 생각했던 것 대로, 최솟값을 가지려면 적어도 한 전선 이상은 최단거리로 연결되어야 함을 이야기하고 있었다.

 

그래서 결론은, 한 점을 최단거리로 연결하고, 그 경로를 기록해 둔다. 두 번째 전선을 연결할 때, 서로 전선이 중첩되지 않게 기록해둔 경로를 방문 처리해둔다. 그리고 두번째 전선을 연결한다.

그래서 문제 힌트의 (2)를 확인하기 위해 BFS를 두번실행해야 한다. (3)의 예도 있기 때문에 BFS를 총 4번 해야한다.

 

2번의 BFS 중 모두 연결할 수 없다면 impossible을,

그렇지 않다면 두 번의 예중 최솟값을 선택하여 출력한다.

5. 코드

#include <cstdio>
#include <queue>
#include <string.h>
using namespace std;

struct COORD {
	COORD() {}
	COORD(int y_, int x_, int dist_) :y(y_), x(x_), dist(dist_) {}
	int y, x, dist;
	
};

COORD a[2], b[2]; 
int n, m;
int ans1, ans2;

const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };


int bfs(COORD fst[2], COORD snd[2]) 
{
	queue<COORD> q;
	bool visited[101][101] = { false };
	int parent[101][101];
	memset(parent, -1, sizeof(parent));

	for (int i = 0; i < 2; ++i)
		visited[snd[i].y][snd[i].x] = true;
	

	q.push(fst[0]);
	visited[fst[0].y][fst[0].x] = true;
	int fst_dist = 0;

	while (!q.empty()) 
	{
		COORD cur = q.front(); q.pop();

		if (cur.x == fst[1].x && cur.y == fst[1].y) {
			fst_dist = cur.dist;
			break;
		}

		for (int dir = 0; dir < 4; ++dir) {
			COORD next;
			next.y = cur.y + dy[dir];
			next.x = cur.x + dx[dir];
			next.dist = cur.dist + 1;
			if (next.y < 0 || next.x < 0 || next.y > m || next.x > n || visited[next.y][next.x])
				continue;

			q.push(next);
			visited[next.y][next.x] = true;
			parent[next.y][next.x] = dir;
		}
	}

	memset(visited, false, sizeof(visited));
	COORD cur = fst[1];
	visited[cur.y][cur.x] = true;
	while (!(cur.x == fst[0].x && cur.y == fst[0].y)) 
	{
		if (parent[cur.y][cur.x] == 0) {
			cur.x -= 1;
		}
		else if (parent[cur.y][cur.x] == 1) {
			cur.x += 1;
		}
		else if (parent[cur.y][cur.x] == 2) {
			cur.y -= 1;
		}
		else if(parent[cur.y][cur.x] == 3) {
			cur.y += 1;
		}
		visited[cur.y][cur.x] = true;
	}


	q = queue<COORD>();
	q.push(snd[0]);
	visited[snd[0].y][snd[0].x] = true;
	int snd_dist = 0;

	while (!q.empty()) 
	{
		cur = q.front(); q.pop();
		if (cur.x == snd[1].x && cur.y == snd[1].y) {
			snd_dist = cur.dist;
			break;
		}

		for (int dir = 0; dir < 4; ++dir) {
			COORD next;
			next.y = cur.y + dy[dir];
			next.x = cur.x + dx[dir];
			next.dist = cur.dist + 1;
			if (next.y < 0 || next.x < 0 || next.y > m || next.x > n || visited[next.y][next.x])
				continue;

			q.push(next);
			visited[next.y][next.x] = true;
			parent[next.y][next.x] = dir;
		}
	}

	if (snd_dist == 0)
		return 987654321;
	else
		return snd_dist + fst_dist;
}

int main()
{
	scanf("%d %d", &n, &m);
	scanf("%d %d", &a[0].x, &a[0].y);
	scanf("%d %d", &a[1].x, &a[1].y);
	scanf("%d %d", &b[0].x, &b[0].y);
	scanf("%d %d", &b[1].x, &b[1].y);
	
	
	//a1이 최단인 경우
	ans1 = bfs(a, b);

	//b1이 최단인 경우
	ans2 = bfs(b, a);

	if (ans1 == 987654321 && ans2 == 987654321)
		printf("IMPOSSIBLE\n");
	else
		printf("%d\n", min(ans1, ans2));
	
	return 0;
}

 

6. 결과