[SW Expert] BFS 문제 - 보급로

문제는 삼성 SW Expert 의 1249번 문제. 코드 유출하지 말라니까 문제는 직접 들어가서 보기를 권장한다. (다른 사람들은 다 올렸던데 ...)

 

https://swexpertacademy.com/main/code/problem/problemDetail.do

 

짜증나는게 컴파일러가 C++ 밖에 없어서 어쩔수 없이 C 코드를 C++로 일부 바꿔서 작성하였다. 정답 코드는 아래와 같다.

 

#include <iostream>
using namespace std;

#define MAX 101
#define INFI 99999

typedef struct Queue {
	int x;
	int y;
} Queue;


int G[MAX][MAX];
int D[MAX][MAX];

Queue Q[9999999];
int front = -1;
int rear = -1;

int BFS (int size) {
	// D값 모두 최고값으로 초기화
	for (int y = 0; y < MAX; y++) {
		for (int x = 0; x < MAX; x++) {
			D[y][x] = INFI;
		}
	}
	
	// 큐에 첫번째 좌표 등록
	rear++;
	Q[rear].x = 0;
	Q[rear].y = 0;
	
	// 출발지 최단거리 설정
	D[0][0] = 0;
	
	// 방문 표시
	Visited[0][0] = 1;
	
	// BFS 시작
	while (front < rear) {
		// 큐에서 꺼내기
		front++;
		
		int x = Q[front].x;
		int y = Q[front].y;
		
		// 왼
		if (x - 1 >= 0) {
			if (D[y][x - 1] > D[y][x] + G[y][x - 1]) {
				rear++;
				Q[rear].x = x - 1;
				Q[rear].y = y;
				D[y][x - 1] = D[y][x] + G[y][x - 1];
			}
		}
		
		// 오
		if (x + 1 < size) {
			if (D[y][x + 1] > D[y][x] + G[y][x + 1]) {
				rear++;
				Q[rear].x = x + 1;
				Q[rear].y = y;
				D[y][x + 1] = D[y][x] + G[y][x + 1];
			}
		}
		
		// 위
		if (y - 1 >= 0) {
			if (D[y - 1][x] > D[y][x] + G[y - 1][x]) {
				rear++;
				Q[rear].x = x;
				Q[rear].y = y - 1;
				D[y - 1][x] = D[y][x] + G[y - 1][x];
			}
		}
		
		// 아
		if (y + 1 < size) {
			if (D[y + 1][x] > D[y][x] + G[y + 1][x]) {
				rear++;
				Q[rear].x = x;
				Q[rear].y = y + 1;
				D[y + 1][x] = D[y][x] + G[y + 1][x];
			}
		}
	}
	
	return D[size - 1][size - 1];
}

void initGraph () {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			G[i][j] = 0;
			D[i][j] = 0;
			Visited[i][j] = 0;
			
			front = -1;
			rear = -1;
		}
	}
}

int main(void) {
	int tc = 0;
	int size = 0;
	
	cin >> tc;
	
	for (int i = 0; i < tc; i++) {
		cin >> size;
	
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				scanf("%1d", &G[i][j]);
			}
		}
		
		cout << "#" << i + 1 << " " << BFS(size) << endl;
		
		initGraph();
	}
	
	// your code goes here
	return 0;
}

 

이 문제를 풀면서 어려웠던 점은 아래와 같다.

 

1. 일반적으로 최소 비용 문제는 정점 방문 시 이미 방문한 곳은 다시는 방문하지 않지만, 이 문제는 방문한 정점도 다시 체크해서 갱신해야 한다. 이 문제는 맵의 모든 곳을 이동할 수 있기 때문이다. 고정관념 때문에 방문한 곳은 재방문하지 않도록 코드를 짜다보니 최소 값이 아닌 누적 값이 계속 나오게 되었다. (왼 > 오 > 위 > 아 순으로 이동 시 최소 누적치. 몰론 재방문 하지 않도록 짜는 방법도 있지만 내머리는 무리.)

 

2. 최소 비용을 누적시킬 방법에 대해 상당히 많이 고민했다. 구조체에 하나하나 넣어서 누적하기에는 간선 완화 방법이 어려운데 그부분을 오랜시간 고민했다.

 

3. 테스트 케이스가 10개인데 값이 작은 부분은 답이 잘 나왔지만 값이 커지니까 오차가 생겼다. 문제 특성상 모든 정점을 돌아야 하므로 큐가 비워지는 시점 이후에 답을 리턴해야 하는데, 큐가 비어지지도 않았는데 도착지점에 왔다고 리턴해버려서 값이 아주 약간 틀어지는 문제가 생겼다. (여기서 2시간 날라갔죠 ...)

 

이 문제에서 짚고 넘어가야할 개념은 아래와 같다.

 

간선 완화

 

시작 지점 S 부터 도착 지점 V까지의 한번에 가는 경로는 D[v] 로 표현 할 수 있다. S부터 V까지 한번에 가는 비용보다 중간지점인 U를 거쳐서 가는 경로가 있다고 하면 D[u] + G[u][v] (가중치) 로 표현할 수 있다. 만약에 시작 지점에서 도착 지점까지 한번에 가는 경로보다 경유지를 거쳐서 가는 비용이 적은지 확인 하려면 아래와 같이 확인 할 수 있다.

 

if (D[v] > D[u] + G[u][v]) {
	D[v] = D[u] + G[u][v];
}

 

이렇게 출발지부터 목적지까지 가장 작은 비용으로 계속 갱신하는 방법을 간선 완화라고 한다.