DFS+간단테크닉 문제 혹은 DFS+BFS

문제

주어진 지도에서 1구역, 2구역이 주어진다.

1구역에서 2구역으로 상하좌우 한칸씩 이동할 수 있다.

1구역에서 2구역으로 갈 수 있는 최단 거리를 구하라.

 

입력

N은 행, M은 열이며 map이 0과 1로 구분되어 입력된다.

0은 이동경로이며 1은 구역을 의미한다.

 

6 16

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0

0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0

0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0

0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0

0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0

 

 

출력

4

---

접근방법1

1. map 전체를 탐색하여 1구역을 DFS로 확산하며 좌표를 저장한다.

2. 이때 1구역의 값을 바꾸어 구분해준다.

3. 2구역을 for문으로 탐색하며 좌표를 저장한다.

4. 1구역과 2구역 전체 좌표를 대조하여 최소 이동거리를 구한다.

 

※ 최소이동거리

피타고라스 정리에 의하면 아래와 같다.

단, 좌표의 움직임이 상하좌우로 제한되어 있다면, 이동거리는 |x2 - x1| + |y2 - y1|이다.

 

 

방법1의 풀이는 아래와 같다.

#include <stdio.h>

#define MAX ((int)(1e6))

int N; //행
int M; //열
int map[50+10][50+10];
int visit[50+10][50+10];

int minCnt=MAX;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

struct Coordinate{
	int r;
	int c;
}typedef Coordi;

Coordi L1[50*50];
Coordi L2[50*50];
int idxL1=0;
int idxL2=0;


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

void MyPrint(){
	printf("\n");
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}
}

void FindFactory(int x, int y){
	//printf("CR (%d,%d),idx: %d\n",x,y);
	//종료조건
	if(map[x][y]==0){
		//printf("RETURN (%d,%d),idx: %d\n",x,y);
		return;
	}
	
	//방문 표시
	visit[x][y]=1;
	
	//map값 변경
	map[x][y]=2;
	L1[idxL1].r = x;
	L1[idxL1].c = y;
	idxL1++;
	//확산
	for(int i=0; i<4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(nx <0 || nx > N-1 || ny < 0 || ny > M-1 || visit[nx][ny] == 1) continue;
		FindFactory(nx,ny);	
		
	}
}

int ABS(int data){
	return data > 0 ? data : -data;
}


void Calc(){
	for(int i=0; i<idxL1; i++){
		for(int j=0; j<idxL2; j++){
			int gap = ABS(L1[i].r - L2[j].r) + ABS(L1[i].c - L2[j].c);
			//printf("gap : %d\n",gap);
			if(minCnt > gap) minCnt = gap;
		}
	}
}



int main() {
	Input();
	//MyPrint();
	int compareFlag=0;
	
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			visit[i][j]=0;
		}
	}
	
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			
			if(map[i][j]==1){
				FindFactory(i,j);
				compareFlag=1;
			}
			if(compareFlag) break;
		}
		if(compareFlag) break;
	}
	
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			if(map[i][j]==1)
			{
				L2[idxL2].r=i;
				L2[idxL2].c=j;
				idxL2++;
			}
		}
	}
	
	Calc();

	printf("%d\n", minCnt-1);
	
	return 0;
}

 

---

BFS로 접근하는 풀이방법도 있을 수 있겠다. 이 편이 더 간단하려나..

 

접근방법2

1. 구역의 좌표 전체를 출발점으로 생각한다.

2. DFS로 구역을 찾는다. 찾으면서 좌표를 Enque한다.

3. BFS로 Queue에 모든 좌표를 출발점으로 넣고 확산시킨다.

4. 확산하면서 다음 구역이 나올때까지 반복한다.

 

#include <stdio.h>

int N;
int M;
int map[50+10][50+10];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

struct Coordinate{
	int x;
	int y;
	int cnt;
}typedef Coordinate;

Coordinate myque[50*50+10];
int rp;
int wp;


void Enque(int x, int y, int cnt){
	map[x][y]=3;
	Coordinate data;
	data.x = x;
	data.y = y;
	data.cnt = cnt;
	myque[wp] = data;
	wp++;
}

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

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

void StartQue(){
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			if(map[i][j]==2){
				DFS(i,j);
				return;
			}
		}
	}
}

void DFS(int x, int y){
	if(map[x][y] != 2){
		return;
	}
	
	//visit 배열 대신 map을 바꾸자
	map[x][y]=3;
	Enque(x,y,0);
	
	//확산
	for(int i=0; i<4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		DFS(nx,ny);
	}
}

int BFS(){
	//초기화
	rp=0; wp=0;
	//초기Inque
	StartQue();
	//반복
	while(rp<wp){
		Coordinate cur = Deque();
		
		for(int i=0; i<4; i++){
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if(map[nx][ny]==2){
				return cur.cnt;
			}
			if(map[nx][ny]!=1) continue;
			Enque(nx,ny,cur.cnt+1);
		}
	}
}

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