[백준] 다리 만들기 (DFS, BFS)

아 드디어 나를 엄청나게 괴롭히던 다리 만들기 문제를 풀었다. 이 문제는 조건이 복잡해서 최대한 단순하게 생각하는 게 좋은데, 너무 어렵게 생각해서 며칠을 못 풀었던 문제다.

 

백준 2146번 다리 만들기 문제

 

입력 값은 아래와 같다.

 

10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

 

이 문제에서 며칠을 막힌 이유는 육지의 끝부분마다 다른 섬까지 도착하는 모든 경우의 수를 구하면 시간 초과가 일어나지 않을까하는 걱정때문이었다. 하지만 컴퓨터는 내 생각보다 허접하지 않았다. 코드는 아래와 같다.

 

#include <stdio.h>
#define MAX 100
#define INFI 99999999

// 맵과 방문 기록
int Map[MAX][MAX];
int Visited[MAX][MAX];

// 육지끝 좌표 저장
typedef struct Position {
	int x;
	int y;
	int c;
} Position;

Position P[MAX * MAX];
int front = -1, rear = -1;

// 왼, 오, 위, 아
int px[] = {-1, 1, 0, 0};
int py[] = {0, 0, -1, 1};

// 섬번호 매기기
void DFS (int y, int x, int limit, int number) {
	// 방문 표시
	Visited[y][x] = 1;
	
	// 섬번호 매기기
	Map[y][x] = number;
	
	// 4방향 체크
	for (int i = 0; i < 4; i++) {
		// 이동할 좌표 계산
		int nx = px[i] + x;
		int ny = py[i] + y;
		
		// 이동할 좌표가 유효한지 체크
		if (nx < 0 || nx >= limit || ny < 0 || ny >= limit) {
			continue;
		}
		
		// 방문하지 않았다면 추가
		if (Map[ny][nx] > 0 && !Visited[ny][nx]) {
			DFS(ny, nx, limit, number);
		}
	}
}

// 육지 끝에서 다른 육지까지 BFS 탐색 시작
int BFS (int start, int limit) {
	int Result = INFI;
	
	// BFS를 돌릴 큐에 startV와 다른 좌표를 넣는다.
	for (int y = 0; y < limit; y++) {
		for (int x = 0; x < limit; x++) {
			// 시작점을 큐에 넣는다.
			if (Map[y][x] == start) {
				rear++;
				P[rear].x = x;
				P[rear].y = y;
				P[rear].c = 0;
				
				// 탐색 시 시작지점은 방문하지 않도록 방문 표시
				Visited[y][x] = 1;
			}
		}
	}
	
	// 탐색 시작
	while (front < rear) {
		front++;
		
		// 이동할 좌표 확인
		int x = P[front].x;
		int y = P[front].y;
		int c = P[front].c;
		
		// 왼, 오, 위, 아
		for (int i = 0; i < 4; i++) {
			// 이동할 좌표 계산
			int nx = px[i] + x;
			int ny = py[i] + y;
			
			// 이동할 좌표가 유효한지 체크
			if (nx < 0 || nx >= limit || ny < 0 || ny >= limit) {
				continue;
			}
			
			// 이동하려는 위치가 육지이고, 다른 섬이라면 거리 계산
			if (Map[ny][nx] != 0 && Map[ny][nx] != start) {
				// 최소 거리 구하기
				if (Result > c) {
					Result = c;
					break;
				}
			}
			// 이동하려는 위치가 바다이고, 방문하지 않았다면 이동
			else if (Map[ny][nx] == 0 && !Visited[ny][nx]) {
				rear++;
				P[rear].x = nx;
				P[rear].y = ny;
				P[rear].c = c + 1;
				
				// 방문 표시
				Visited[ny][nx] = 1;
			}
		}
	}
	
	return Result;
}

// 방문 기록 초기화
void initVisited () {
	for (int y = 0; y < MAX; y++) {
		for (int x = 0; x < MAX; x++) {
			Visited[y][x] = 0;
		}
	}
}

int main(void) {
	int N = 0;
	int R = 0;
	int Min = INFI;
	int Number = 1;
	
	scanf("%d", &N);
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			scanf("%d", &Map[y][x]);
		}
	}
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			// 육지가 검색되고 방문하지 않은 곳이라면
			if (Map[y][x] > 0 && !Visited[y][x]) {
				DFS(y, x, N, Number);
				Number++;
			}
		}
	}
	
	// 방문 기록 초기화
	initVisited();
	
	// 모든 섬에 대해 최소 값을 찾아야 한다.
	for (int i = 1; i < Number; i++) {
		R = BFS(i, N);
		Min = (Min > R) ? R : Min;
		
		// 큐 초기화
		rear = -1;
		front = -1;
		
		// 방문 기록 초기화
		initVisited();
	}
	
	printf("%d\n", Min);

	return 0;
}

 

이 문제를 풀기 위해서 맵에서 섬마다 식별할 수 있는 값으로 넣어주는 것이 좋다. DFS로 맵을 탐색하여 육지가 검색되면, 다른 섬인 것을 식별할 수 있도록 중복되지 않는 값을 넣는다. 이후에 섬을 식별할 수 있는 값만큼 반복문으로 돌리면서 BFS로 바다일 경우에만 이동하면서 비용을 추가한다. BFS를 할 때 주의할 점은 큐에 데이터를 넣는 부분이다.

 

// BFS를 돌릴 큐에 startV와 다른 좌표를 넣는다.
for (int y = 0; y < limit; y++) {
  for (int x = 0; x < limit; x++) {
    // 시작점을 큐에 넣는다.
    if (Map[y][x] == start) {
      rear++;
      P[rear].x = x;
      P[rear].y = y;
      P[rear].c = 0;

      // 탐색 시 시작지점은 방문하지 않도록 방문 표시
      Visited[y][x] = 1;
    }
  }
}

 

BFS를 하기 위해서 큐에 좌표를 넣을 때 출발지 섬의 좌표를 넣어준다. 섬의 끝부분의 좌표를 저장해서 큐에 넣는 방법으로 해도 상관 없을 것 같다. (내가 이렇게 했다가 자꾸 틀어져서 좀 더 쉽게 생각하기로 했다.)

 

BFS 탐색 시 조건은 두가지로 나뉘는데 이동 조건 (이동할 위치가 바다이고, 방문하지 않은 곳) 과 도착 조건 (이동할 위치가 섬이고, 시작 지점의 ID와 다른 곳) 이다. 

 

// 이동하려는 위치가 육지이고, 다른 섬이라면 거리 계산
if (Map[ny][nx] != 0 && Map[ny][nx] != start) {
  // 최소 거리 구하기
  if (Result > c) {
  	Result = c;
 	break;
  }
}
// 이동하려는 위치가 바다이고, 방문하지 않았다면 이동
else if (Map[ny][nx] == 0 && !Visited[ny][nx]) {
  rear++;
  P[rear].x = nx;
  P[rear].y = ny;
  P[rear].c = c + 1;

  // 방문 표시
  Visited[ny][nx] = 1;
}

 

이 조건에 맞게 BFS를 진행하면서 최소 비용을 단계마다 저장한 후, 도착 조건에서 가장 작은 비용으로 업데이트한다. 도착 지점 이후에는 다른 방향도 검사를 해야 하기 때문에, break로 반복문을 종료한다. 이렇게 하면 이후에 다른 방향으로 이동하여 체크가 가능하다.

 

정말 힘들었는데, 풀고 보니 그냥 DFS, BFS 두 개 사용한 문제였다. 그런데 이게 생각이 안 나니까 시간을 미친 듯이 잡아먹는다. 경험이 부족한 것으로...