코딩인터뷰완전분석 : 자외선을 피해가기(BFS) + Heap

문제내용 :

영희는 자외선이 피부에 좋지 않기 때문에 이동 시 자외선에 노출되는 것을 최소한으로 하고 싶어서 가는 길의 자외선 양을 모두 조사하였다.

N*N 모양의 장소의 모든 길의 자외선 양이 주어지고 영희는 상하좌우 한 칸씩만 이동이 가능하다.      
시작점(1,1)에서 도착점(N,N)까지 이동 시 자외선 합의 최소값을 찾아라.
예를 들어 3*3 장소의 자외선 양이 아래와 같다면 오른쪽처럼 이동하면 8만큼만 노출된다.

 

입력    첫 줄에 N(2≤N≤100)이 들어온다.    그 다음 줄부터 N개의 줄에 각각 N개씩 M(0≤M≤9)이 공백 없이 들어온다.

출력    출발점에서 도착점까지 자외선 합의 최소값을 출력한다.

 

풀이 :

#include <stdio.h>
#define MAX 101
#define SWAP(a, b, type) {type t;t=b;b=a;a=t;}
int map[MAX][MAX];
int sum[MAX][MAX];
typedef struct _que {
	int r, c;
	int sum;    //heap으로 풀기 위해 sum 필요
}QUE;
QUE que[MAX * MAX * MAX];

//heap으로 풀기
int last_node = 0;
QUE heap[MAX * MAX];
int visited[MAX][MAX];
void heap_push(int r, int c, int sum) {
	if (last_node == MAX * MAX) {
		//full
		return;
	}
	heap[++last_node].r = r;
	heap[last_node].c = c;
	heap[last_node].sum = sum;

	//부모 타고 올라가기
	int p_p, c_p;
	c_p = last_node; p_p = c_p / 2;
	while (p_p > 0) {
		if (heap[p_p].sum > heap[c_p].sum) {
			SWAP(heap[p_p], heap[c_p], QUE);
			//부모타고 올라가기
			c_p = p_p;
			p_p = c_p / 2;
		}
		else {
			return;
		}
	}
	return;
}
void heap_pop(QUE* d) {
	if (last_node == 0) {
		//empty
		return;
	}
	//팝은 무조건 1번째 원소
	*d = heap[1];
	heap[1] = heap[last_node--];
	int p_p, c_p, l_p, r_p;
	p_p = 1;
	l_p = p_p * 2;
	r_p = l_p + 1;
	while (l_p <= last_node) {
		//자식이 하나
		if (l_p == last_node) {
			c_p = l_p;
		}
		else {
			//자식이 둘
			c_p = (heap[l_p].sum < heap[r_p].sum ? l_p : r_p);
		}
		if (heap[p_p].sum > heap[c_p].sum) {
			SWAP(heap[p_p], heap[c_p], QUE);
			p_p = c_p;
			l_p = p_p * 2;
			r_p = l_p + 1;

		}
		else {
			return;
		}
	}
	return;
}
int rp, wp;
int N;
int dr[4] = { 0,1,0,-1 }, dc[4] = { 1,0,-1,0 }; //동남서북(0123)
void In_Que(int r, int c) {
	que[wp].r = r;
	que[wp].c = c;
	wp++;
}
QUE Out_Que(QUE* q) {
	return que[rp++];
}
//int BFS() {
//  int i, nr, nc;
//  QUE q;
//  In_Que(1, 1);
//  sum[1][1] = map[1][1];
//  while (rp < wp) {
//      q = Out_Que(&q);
//      for (i = 0; i < 4; i++) {
//          nr = q.r + dr[i]; nc = q.c + dc[i];
//          if (nr<1 || nr>N || nc<1 || nc>N)continue;
//          if (sum[q.r][q.c] + map[nr][nc] < sum[nr][nc]) {
//              //현재의 해가 더 최소이면 큐에 저장(기록)
//              In_Que(nr, nc);
//              sum[nr][nc] = sum[q.r][q.c] + map[nr][nc];  //기록
//          }
//      }
//  }
//  return sum[N][N];   //큐가 빈 상태(더 좋은 해가 만들어지지 않을 때까지)
//}

//heap으로 짜보기
int BFS() {
	int i, nr, nc;
	QUE q;
	heap_push(1, 1, map[1][1]);
	visited[1][1] = 1;
	while (last_node > 0) {
		heap_pop(&q);
		if (q.r == N && q.c == N) return q.sum;
		for (i = 0; i < 4; i++) {
			nr = q.r + dr[i]; nc = q.c + dc[i];
			if (nr<1 || nr>N || nc<1 || nc>N)continue;
			if (visited[nr][nc] == 1) continue;
			visited[nr][nc] = 1;
			heap_push(nr, nc, q.sum + map[nr][nc]);
		}
	}
}
void input() {
	int i, j;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++) {
			scanf("%1d", &map[i][j]);
			//sum[i][j] = 0x7fffffff;   //큰 값 대입
		}
	}
}
int main() {
	input();
	printf("%d\n", BFS());
	return 0;
}

 

BFS :자신이 이동하면서 현재 위치에서 다음에 갈 자외선+지금까지의 자외선의 합이 다음 위치에서의 자외선의 합보다 작다면 기록. 이런식으로 작은값만 찾아서 큐에 넣고 하나씩 빼보면서 끝날 때 까지 비교.

 

Heap : 힙트리에 push 하고 pop 하면 가장 작은값이 나오기 때문에 그 작은 값들로 최종 조건이 끝날 때 까지 반복.