룩업테이블 활용, DFS, BFS

룩업테이블이랑 예상된 결과값을 미리 계산하여 놓은 배열과 같은 집합을 의미한다.

알고리즘 해결에 있어 룩업테이블을 활용해야하는 경우가 있다.

아래의 문제를 살펴보자

 

문제

주어진 map은 감염경로와 같다.

N*N크기의 map에 숫자가 입력되어 주어지며 숫자는 미로의 길을 의미하는데 아래와 같은 정보를 가진다.

지도의 크기 N과, 병균의 위치가 주어진다.

병균은 주어진 지도의 경로를 통해서만 전염된다고 한다. 주어진 map에서 감염되지 않은 경로의 수를 구하라.

 

입력

4

0 0

2799

7439

0652

2172

 

출력

5

 

---

해결전략1-DFS

1. 주어진 좌표에서 DFS로 확산한다.

2. 확산시에는 방문하지 않은 경로, 경로가 연결된 지점만 확산한다.

3. 각 도로 모양에 따른 상하좌우 방문정보를 미리 Table로 저장한다. -> Look up Table

4. Look up Table의 인덱스는 각 도로의 모양이며 1은 방향을 의미한다. 방문 순서는 상하좌우로 고정한다.

5. 현재 좌표에서 확산할 수 있는 경로가 있는지 확인하며 확산할 다음 좌표에서 확산 받을 수 있는 경로가 있는지 확인한다.

상 -> 하, 하->상, 좌->우, 우->좌로 확산할 수 있기때문에 dir배열을 만들어 idx값을 미리 만들어놓는다.

상=0, 하=1. 좌=2. 우=3

#include <stdio.h>

int N;
int startX;
int startY;
int map[11][11];
int visit[11][11];
int dx[4]={-1,1,0,0}; //상하좌우
int dy[4]={0,0,-1,1};
//방문순서 상하좌우
int lookup[][4]={
	{0,0,0,0}, //0
	{0,0,1,1}, //1
	{1,1,0,0}, //2
	{0,1,0,1}, //3
	{0,1,1,0}, //4
	{1,0,1,0}, //5
	{1,0,0,1}, //6
	{1,1,0,1}, //7
	{0,1,1,1}, //8
	{1,1,1,0}, //9
	{1,0,1,1}, //10
	{1,1,1,1}, //11
};

int dir[4]={1,0,3,2};

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

int Count(){
	int cnt =0;
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(map[i][j] != 0 && visit[i][j] ==0 ) cnt++;
		}
	}
	
	return cnt;
}

void Dfs(int x, int y){
	if(map[x][y]==0) return;
	visit[x][y] = 1;
	
	for(int i=0; i<4; i++) //상하좌우
	{
		int nx = x+ dx[i];
		int ny = y+ dy[i];
		
		if(0 > nx || nx >= N || 0 > ny || ny >= N || visit[nx][ny] == 1 ) 
		{
			continue;
		}
		if(lookup[map[x][y]][i]==1 && lookup[map[nx][ny]][dir[i]]==1)//확산
		{
			Dfs(nx, ny);
		}
	}
}

int main() {
	Input();
	
	Dfs(startX, startY);
	
	int ans = Count();
	
	/*
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			printf("%d ",visit[i][j]);
		}
		printf("\n");
	}
	*/
	
	printf("%d",ans);
	return 0;
}

---

해결전략2-BFS

동일하게 BFS로 할 수도 있다. 방문 노드의 순서만 다를 뿐 성능은 동일하겠다.

전체 경로 수 - 방문한 경로를 빼주면 된다.

#include <stdio.h>

int N;
int startX;
int startY;
int map[11][11];
int visit[11][11];
int dx[4]={-1,1,0,0}; //상하좌우
int dy[4]={0,0,-1,1};
//방문순서 상하좌우
int lookup[][4]={
	{0,0,0,0}, //0
	{0,0,1,1}, //1
	{1,1,0,0}, //2
	{0,1,0,1}, //3
	{0,1,1,0}, //4
	{1,0,1,0}, //5
	{1,0,0,1}, //6
	{1,1,0,1}, //7
	{0,1,1,1}, //8
	{1,1,1,0}, //9
	{1,0,1,1}, //10
	{1,1,1,1}, //11
};

int dir[4]={1,0,3,2};

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

Q myque[10*10*10];
int rp, wp;

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

int Count(){
	int cnt =0;
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(map[i][j] != 0) cnt++;
		}
	}
	
	return cnt;
}

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

Q Deque(){
	Q data;
	data = myque[rp];
	rp++;
	return data;
}

int Bfs(){
	//초기화
	rp=0;
	wp=0;
	int cnt =0;
	//첫출발
	Enque(startX,startY);
	//반복
	while(rp<wp){
		Q cur = Deque();
		for(int i=0; i<4; i++){
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if(nx < 0 || nx >= N || ny < 0 || ny >= N ) continue;
			if(visit[nx][ny] == 1) continue;
			if((lookup[map[cur.x][cur.y]][i] == 1) && (lookup[map[nx][ny]][dir[i]]==1)){
				Enque(nx, ny);
				visit[nx][ny]=1;
				cnt++;
			}
		}
	}
	
	return cnt;
}

int main() {
	Input();
	int ans = Bfs();
	int total = Count();
	
	printf("%d",total-ans);
	return 0;
}