[백준 5022] 연결

https://www.acmicpc.net/problem/5022

5022번: 연결

#include <cstdio>
#include <queue>
#include <algorithm>
int N, M;
struct _st
{
	int sx, sy;
	int ex, ey;
}Points[2 + 2];

struct _vt
{
	int x, y;
};


struct _qt
{
	int x, y;
	std::vector<_vt> path;
};

std::queue<_qt> Q;
int visited[100 + 5][100 + 5];
int move[100 + 5][100 + 5];

int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };


void input()
{
	scanf("%d %d", &M, &N);
	scanf("%d %d %d %d", &Points[0].sy, &Points[0].sx, &Points[0].ey, &Points[0].ex);
	scanf("%d %d %d %d", &Points[1].sy, &Points[1].sx, &Points[1].ey, &Points[1].ex);
}


int BFS(int type, int x, int y)
{
	Q = {};
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);

	_qt start = {};
	start.x = x;
	start.y = y;
	start.path.push_back({ x, y });
	Q.push(start);
	visited[x][y] = 1;
	bool set = false;

	_qt data = {};
	while (!Q.empty()) {
		data = Q.front();
		Q.pop();

		if (data.x == Points[type].ex && data.y == Points[type].ey) {
			set = true;
			break;
		}

		for (int p = 0; p < 4; p++) {
        		_qt ndata = {};
			ndata.x = data.x + dir_x[p];
			ndata.y = data.y + dir_y[p];

			if (ndata.x < 0 || ndata.x > N || ndata.y < 0 || ndata.y > M) continue;
			if (ndata.x == Points[1 - type].sx && ndata.y == Points[1 - type].sy) continue;
			if (ndata.x == Points[1 - type].ex && ndata.y == Points[1 - type].ey) continue;
			if (visited[ndata.x][ndata.y]) continue;	// 이미 방문한 곳 스루
			if (move[ndata.x][ndata.y]) continue;		// A나 B가 이미 깔려있는 곳으로는 가지 못함 
			ndata.path.clear();
			for (_vt road : data.path) {
				ndata.path.push_back({ road.x, road.y });
			}
			ndata.path.push_back({ ndata.x, ndata.y });
			Q.push({ ndata });
			visited[ndata.x][ndata.y] = visited[data.x][data.y] + 1;
		}
	}
	if (set == false) return -1;

	for (_vt route : data.path) {
		move[route.x][route.y] = type + 1;	// 이동 경로표시
	}
	return visited[data.x][data.y] - 1;
}



int main()
{
	input();
	// A 먼저 깔아본다 
	std::fill(&move[0][0], &move[0][0] + sizeof(move) / sizeof(int), 0);
	int res1_A = BFS(0, Points[0].sx, Points[0].sy);
	int res1_B = BFS(1, Points[1].sx, Points[1].sy);
	int total1 = res1_A + res1_B;

	// B 먼저 깔아본다 
	std::fill(&move[0][0], &move[0][0] + sizeof(move) / sizeof(int), 0);
	int res2_B = BFS(1, Points[1].sx, Points[1].sy);
	int res2_A = BFS(0, Points[0].sx, Points[0].sy);
	int total2 = res2_A + res2_B;


	if (res1_B == -1 && res2_A == -1) printf("IMPOSSIBLE\n");
	else {
		int min = 0x7fffffff;
		if (res1_B == -1) min = total2;
		else if (res2_A == -1) min = total1;
		else if (res1_B != -1 && res2_A != -1) min = (total1 > total2) ? total2 : total1;
		printf("%d\n", min);
	}

	return 0;
}

1. "두 직선은 접하면 안된다" 라는 조건 때문에 무진장 애를 먹었다. 

=> BFS에서 상태발전을 위한 Q를 생성할 때 지나온 경로들의 좌표를 저장하기 위한 path 벡터를 선언해 주었다. 위의 코드의 경우 행과 열을 반대로 받았기 때문에 문제에서의 좌표평면이 아니라 행렬로 생각해 본다면, (1, 5)에 도달하였을 때 path에 들어있는 좌표는 (1, 2) (1, 3) (1, 4) 이다. 그리고 마지막에 자기 자신 좌표를 push_back 해준다. 

 

BFS를 통해 최단거리를 탐색한 후 만약 목적 좌표에 도달했다면, set 플래그를 true로 바꿔주고 실제 경로를 move 배열에 표시해주었다. 

만약 목적 좌표에 도달하지 못했다면 -1을 리턴해 주었다. 

 

2. 이 조건과 더불어 필요한 전선의 최솟값을 구해야 하기 때문에 BFS를 4번 돌려야 한다.

=> (1)A 최소로 깔고 + (2)B 깔기,  (3)B 최소로 깔고 + (4)A 깔기

=> BFS를 실행할 때 마다 visited 배열(BFS 탐색 시 사용하는 방문배열) 초기화가 필요하고, move 배열(각 전선의 경로 저장하는 배열)은 (1 + 2) (3 + 4) 번 진행 전에 초기화가 필요하다. 

 

---

++ 22.10.24

경로 표시 재귀로 구현해봄... (1404kb, 0ms)

#include <cstdio>
#include <queue>
#include <algorithm>
int N, M;
struct _st
{
	int sx, sy;
	int ex, ey;
}Points[2 + 2];

struct _qt
{
	int x, y;
};


std::queue<_qt> Q;
int visited[100 + 5][100 + 5];
int move[100 + 5][100 + 5];
_qt path[100 + 5][100 + 5];

int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };


void input()
{
	scanf("%d %d", &M, &N);
	scanf("%d %d %d %d", &Points[0].sy, &Points[0].sx, &Points[0].ey, &Points[0].ex);
	scanf("%d %d %d %d", &Points[1].sy, &Points[1].sx, &Points[1].ey, &Points[1].ex);
}

void path_init()
{
	for (int i = 0; i <= M; i++) {
		for (int j = 0; j <= N; j++) {
			path[i][j] = {};
		}
	}
}


void path_2_move(int x, int y)
{
	// 이동 경로 표시
	if (x == -1 && y == -1) return;

	move[x][y] = 1;
	path_2_move(path[x][y].x, path[x][y].y);
}


int BFS(int type, int x, int y)
{
	Q = {};
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
	
	Q.push({x, y});
	visited[x][y] = 1;
	path[x][y].x = -1;	path[x][y].y = -1;

	_qt data = {};
	while (!Q.empty()) {
		data = Q.front();
		Q.pop();

		if (data.x == Points[type].ex && data.y == Points[type].ey) {
			path_2_move(Points[type].ex, Points[type].ey);
			return visited[data.x][data.y] - 1;
		}

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N || ny < 0 || ny > M) continue;
			if (nx == Points[1 - type].sx && ny == Points[1 - type].sy) continue;
			if (nx == Points[1 - type].ex && ny == Points[1 - type].ey) continue;
			if (visited[nx][ny]) continue;	// 이미 방문한 곳 스루
			if (move[nx][ny]) continue;		// A나 B가 이미 깔려있는 곳으로는 가지 못함 
			Q.push({ nx, ny });
			visited[nx][ny] = visited[data.x][data.y] + 1;
			path[nx][ny].x = data.x; path[nx][ny].y = data.y;
		}
	}
	return -1;
}


int main()
{
	input();
	// A 먼저 깔아본다 
	path_init();
	std::fill(&move[0][0], &move[0][0] + sizeof(move) / sizeof(int), 0);
	int res1_A = BFS(0, Points[0].sx, Points[0].sy);
	path_init();
	int res1_B = BFS(1, Points[1].sx, Points[1].sy);
	int total1 = res1_A + res1_B;

	// B 먼저 깔아본다 
	path_init();
	std::fill(&move[0][0], &move[0][0] + sizeof(move) / sizeof(int), 0);
	int res2_B = BFS(1, Points[1].sx, Points[1].sy);
	path_init();
	int res2_A = BFS(0, Points[0].sx, Points[0].sy);
	int total2 = res2_A + res2_B;


	if (res1_B == -1 && res2_A == -1) printf("IMPOSSIBLE\n");
	else {
		int min = 0x7fffffff;
		if (res1_B == -1) min = total2;
		else if (res2_A == -1) min = total1;
		else if (res1_B != -1 && res2_A != -1) min = (total1 > total2) ? total2 : total1;
		printf("%d\n", min);
	}

	return 0;
}