백준 16137 견우와 직녀 C언어 - BFS 완전탐색

눈물나는 견우와 직녀의 일화이다.

하필이면 절벽지대에 살아가지고 오작교가 없으면 서로가 만나지 못할 수도 있다.

 

문제의 조건은 다음과 같다.

1. 한 칸을 이동하는데 1분이 걸린다.

2. 오작교에 적힌 시간의 배수에만 (0포함) 견우가 다리를 건널 수 있다.

3. 절벽이 교차하는 곳에는 오작교를 놓을 수 없다.

4. 오작교는 연속으로 건널 수 없다.

 

이토록 많은 조건을 뚫고도 견우가 직녀를 만나러 갈 수 있을까?

 

문제 풀이의 청사진은 다음과 같다.

1. 가장 빨리 도착하는 경우를 구해야하므로 BFS 를 이용하여 경로를 찾아본다.

2. 시간복잡도는 정확하게 계산하기 어렵고, 이럴 일도 없지만

N*N (map의 크기) * N * N (0이 들어갈 경우) * N * N( 완전탐색) = 1백만이므로 여유가 차고 넘친다.

 

문제 풀이의 논리는 다음과 같다.

1. 절벽이 교차하는 곳을 제외하고 오작교를 설치할 절벽을 선택하여 최소 시간을 찾는다.

2. 1번을 설치할 수 있는 모든 곳에 대해 수행한다.

 

 

전체코드

#include <stdio.h>
#include <string.h>
#define INF 987654321
int N,  M;
int MAP[11][11];
int visited[11][11];
int dy[] = { 1,0,-1,0 };
int dx[] = { 0,1,0,-1 };
int min = INF;

//queue 구현
typedef struct st {
	int y, x,time;
}CO;
CO queue[11 * 11 * 2];
int wp, rp;
int empty() {
	return wp == rp;
}
void push(int y, int x,int time) {
	queue[wp].y = y;
	queue[wp].time = time;
	queue[wp++].x = x;
}
void pop() {
	rp++;
}
CO front() {
	return queue[rp];
}
void clear() {
	wp = rp = 0;
}

//오작교 설치가 가능한가?
int possible(int y, int x) {
	int row_flag = 0, col_flag = 0;
	if (y + 1 < N && MAP[y+1][x] ==0) col_flag = 1;
	else if (y - 1 >= 0 && MAP[y-1][x]==0)col_flag = 1;
	if (x + 1 < N && MAP[y][x + 1] == 0) row_flag = 1;
	else if (x - 1 >= 0 && MAP[y][x - 1] == 0) row_flag = 1;
	if (col_flag && row_flag) return 0;
	return 1;
}

//bfs수행, 견우(0,0)가 직녀(N-1,N-1)에 도착할 수 있는 최소 시간을 min에 저장.
int bfs(int y, int x, int time) {
	clear();
    //(0,0)에서 시작
	push(y, x,0);
	visited[y][x] = 1;
    
	while (!empty()) {
		CO tmp = front(); pop();
		int y = tmp.y, x = tmp.x, time = tmp.time;
		//현재 시각이 최소로 도착할 수 있는 시각보다 뒤면 더 이상 진행할 필요 없음.
		if (time >= min) break;
        //직녀에게 도착했을 때 최소시간 저장
		if (y == N - 1 && x == N - 1) {
			if (time < min) min=time;
			continue;
		}
        
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
            //범위체크
			if (ny >= N || ny < 0 || nx >= N || nx < 0) continue;
			//일반적인 땅일 경우
			if (MAP[ny][nx] == 1) {
				if (visited[ny][nx]) continue;
				visited[ny][nx] = 1;
				push(ny, nx, time + 1);

			}
			//다리가 있는 경우
			else if (MAP[ny][nx] > 1) {
				//연속으로 오작교를 건널 수 없음
				if (MAP[y][x] > 1) continue;
				if (visited[ny][nx]) continue;
                //건널 수 있는 시간일 경우
				if ((time+1)%MAP[ny][nx]==0 )
					push(ny,nx,time+1);
                //건널 수 없는 시간일 경우 그 자리에서 대기
				else {
					push(y, x, time + 1);
				}
			}

		}
	}
	return 0;
}


int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &MAP[i][j]);
		}
	}
	bfs(0, 0, 0);
	for (int i = 0; i <N; i++) {
		for (int j =0; j<N; j++) {
			if (MAP[i][j] != 0) continue;
			if (!possible(i, j))continue;
				//printf("now y : %d x : %d\n", i, j);
			MAP[i][j] = M;
			memset(visited, 0, sizeof(visited));
			bfs(0,0,0);
			MAP[i][j] = 0;
			
		}
	}
	printf("%d", min);
}

queue 는 struct 구조로 y좌표 x좌표 시각 time 으로 구성되어 있다.

queue 관련 함수는 c++의 <queue> 라이브러리에 해당하는 것과 동일한 기능을 한다. 

단, clear()는 쓰는 위치와 읽는 위치의 값만 0으로 초기화시켜주고 메모리는 그대로 둔다.

 

possible(y,x)함수는 y,x에 오작교 설치가 가능한가를 판단한다.

다시말해 절벽이 교차하는가를 확인한다.

만약 제대로 판단하지 못하는 경우 다음과 같은 예시에서 전혀 다른 답을 도출한다.

7 3 
1 1 1 13 0 0 0
0 0 0 1 1 1 1
1 1 0 1 1 1 1 
1 1 0 1 1 1 1 
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

제대로 절벽을 체크했다면 13이 나오고, 아니라면 12가 나올 것이다.

ㄱ ㅗ 처럼 생긴 절벽과 ㅁ절벽 등 경우를 제대로 제외시켜줘야한다.

 

bfs()에서는 visited가 모두 0일 때를 기준으로 탐색한다. 

오작교 설치가 가능한 절벽을 찾아서 설치한 후 (MAP[y][x] = M;) 견우가 출발한다.

물론 끝난후엔 MAP[y][x] = 0으로 돌려놔야한다.

 

탐색할 때는 가지치기를 위해 최소 시각보다 같거나 큰 시각에 대해서는 수행하지 않는다.

또한 오작교 다음 바로 오작교를 설치할 수 없으므로 MAP[y][x] >1 일 경우 MAP[ny][nx] >1 이어도

건널 수 없으므로 continue 시켜준다.

 

어려운 문제..는 아닌거 같은데(완전탐색이니까)

몇 시간을 투자한건지 모르겠다.

확신이 없어서 자꾸 다른 루트(dfs라던지)를 시도해봐서 그런 것 같다.