[BFS] BFS 이해하기 훈련

문제

N*N 크기의 map이 있음

Input으로 map 크기에 맞는 cost가 들어옴

(0,0) 부터 (N-1,N-1) 까지 가는 최소비용을 구하라

 

입력

N은 2이상 100이하의 자연수이다.

 

3

041

253

620

 

Output

8

---

문제해결

DFS는 모든 경우의 수이다. 시간복잡도가 오래걸릴 수 있다.BFS를 이용하여 최소의 경우를 구할 수 있다. 단 중복방문을 무조건 허용하지 않고 이전 비용보다 좋을때 허용할 수 있도록 한다.

DFS로 최초 풀이해보았으나 N이 커지면 Timeout이 났다. 모든 경우의 수이기때문에 시간복잡도가 매우 높을 것이다.

#include <stdio.h>

int N;
char map[100+10][100+10];
int visit[100+10][100+10];
int dx[4] = {1,0,-1,0}; //하 우 상 좌
int dy[4] = {0,1,0,-1};
int ans=99999999999;

#define IMP 1<<29

void Input(){
	scanf("%d", &N);
	
	for(int i=0; i<N; i++){
		scanf("%s",map[i]);
	}
}

void MyDFS(int x, int y, int cost, int cnt){
	//탈출조건
	if(cnt>2*N-2)
	{
			return;
	}
	
	printf("(%d,%d) : %d _ cnt : %d\n", x, y, cost, cnt);
	
	if(x < 0 || y < 0 || x >= N || y >= N || visit[x][y] != IMP){
		return;
	}
	
	//종료조건
	if(x == N-1 && y == N-1){
		if(cost<ans){
			ans = cost;	
		}
		//printf("RETURN!\n");
		return;
	}
	
	//방문표시
	visit[x][y]=0;
	
	//확산
	for(int i=0; i<4; i++){
		int nx,ny, ncost=0;
		nx = x + dx[i];
		ny = y + dy[i];
		ncost = cost + map[nx][ny]-'0';
		//printf("(%d , %d), %d \n", nx, ny, cost);
		if(0 <= nx && nx < N && 0 <= ny && ny < N ){
			if(visit[nx][ny] > cost + (map[nx][ny] - '0'))
				MyDFS(nx, ny, ncost, cnt+1);
		}
	}
	
	visit[x][y]=IMP;
	
}

int main() {
	Input();
	
	/*
	for(int i=0; i<N; i++){
		printf("%s\n", map[i]);
	}	
	*/
	//초기화
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			visit[i][j]=IMP;
		}
	}
	
	MyDFS(0,0,0,0);
	printf("%d", ans);
	
	return 0;
}

 

경로문제는 십중팔구 DFS혹은 BFS이다. 뭐 아닐수도 있겠지만; 이 문제 역시 BFS로 접근 가능하겠다. 경로의 최소비용이기 때문이다.

BFS의 기본 구조는 다음과 같다.

BFS 기본구조
0. BFS는 Queue자료구조를 사용한다. 따라서 Queue를 만들어놓는다. 
1. 초기화 : BFS에 필요한 read point, write point 나 visit배열 등을 초기화 한다.
2. 출발점 지정 : 초기 출발을 위한 start setting이다. 해당 문제의 경우 0,0에서 출발하기 때문에 해당 노드를 Enque하기로 한다.
3. 확산 : rp가 wp보다 작으면 확산하게, 즉 que가 empty상태가 아니라면 확산하도록 한다. 확산시 deque하여 노드를 가져오고 어떤식으로 확산할지 판단한다. 무조건 확산할 수 없으므로 문제에 따라 확산의 조건을 판별하도록 한다.

 

기본 구조를 생각하면서 가장 중요한 확산의 조건을 세워야한다. 무조건 확산할 수 있겠는가? 그럴 수 없다. 최소cost를 구하는 것이기 때문이다. 그럼 어떻게 접근할 수 있을까?

확산의 위한 조건, 즉 확산하기전에 확산을 할지 말지 판단하는 것이다. BFS에서 확산이란 Enque가 되겠다. 최소cost를 찾기 위해 Enque할 가치가 있다고 판단하는 경우 확산하는 것이다.

확산하려는 곳이 '현재의 비용+확산된 경로의 비용'보다 저렴하다면 확산하면 되지 않을까? 현재의 비용은 map으로 주어진다. 그렇다면 확산된 경로의 누적 비용은 어떻게 구할 수 있을까.

visit배열을 활용하자. visit배열에 확산마다 누적된 값을 기록하는 것이다. 0번 행을 예로 들어보자. (0,0)에서 출발하여 확산을 한다고 가정할 경우 누적치는 아래와 같을 것이다. 이때, 확산 전에 기존의 누적치와 비교하여 cost가 작을 때에만 확산하는 것이다. 

 

노드는 4방향으로 모두 확산하므로 visit배열 (1,1)에서 아래와 같은 경우가 생기게 된다.

0->2를 통해 누적된 경로와 0->4를 통해 누적된 경로가 만나게 되는 것이다. 이때에 더 최소값으로 해당 노드는 cost가 갱신되게 된다. 또한 앞으로의 cost가 누적된 cost보다 작을때만 확산하므로 이전 경로로 다시 되돌아가지도 않는다. 이 부분을 놓치기 쉬운데, 조건을 잘못 수립하게 되면 확산시에 이전경로로 다시 되돌아가는 경우가 생긴다.

이러한 아이디어를 활용하여 visit배열을 만들고 해당 값을 임의의 큰 값으로 설정해주었다.

0,0은 출발지므로 0으로 다시 정의해주도록한다. 이후 BFS 확산을 실시하면 아래와 같은 그림이 될 것이다.

 

#include <stdio.h>
#define MAX (int)(1e6);

int N;
char map[100+10][100+10];
int ans;
int rp;
int wp;
int visit[100+10][100+10];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

struct que{
	int x;
	int y;
}typedef Que;

Que myque[100*100*100];

void Enque(int x, int y)
{
	Que data;
	data.x=x;
	data.y=y;
	myque[wp++] = data;
}

Que Deque()
{
	return myque[rp++];
}

void Input()
{
	scanf("%d", &N);
	for(int i=0; i<N; i++)
	{
		scanf("%s", &map[i]);
	}
}

void BFS(){
	//초기화
	wp=0;
	rp=0;
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			visit[i][j]=MAX;
		}
	}
	//출발지정 (0,0)
	Enque(0,0);
	visit[0][0]=0;
	//반복 및 확산
	
	while(rp<wp)
	{
		Que data = Deque();
		for(int i=0; i<4; i++)
		{
			int nx= data.x + dx[i];
			int ny= data.y + dy[i];
			if(nx<0 || nx>N-1) continue;
			if(ny<0 || ny>N-1) continue;
			//가려는 곳이, visit[nx][ny] > visit[x][y]+map[nx][ny]
			if(visit[nx][ny] > visit[data.x][data.y] + (map[nx][ny]-'0'))
			{
				visit[nx][ny] = visit[data.x][data.y] + (map[nx][ny]-'0');
				Enque(nx,ny);
			}
		}
		
	}
	
	ans = visit[N-1][N-1];
}

int main() {
	
	Input();
	BFS();
	printf("%d",ans);
	return 0;
}