5. 1078 : 저글링 방사능 오염

문제 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=358&sca=50&sfl=wr_subject&stx=%EC%A0%80%EA%B8%80%EB%A7%81&sop=and

JUNGOL | 저글링 방사능 오염 > 문제은행

문제풀이 :

#include<stdio.h>
#define MAX (101)
int map[MAX][MAX]; //지도
int ju[MAX][MAX];
int visit[MAX][MAX]; // 방문체크
// 큐 구조체 설계
typedef struct _node {
	int r, c, time;
}NODE;
NODE que[MAX * MAX]; //큐배열 생성 -> Full 상태 없게 하기 위해 충분히 크게!
int rp, wp;
int R, C, sr, sc, er, ec;
void In_Que(int r, int c, int time) {
	que[wp].r = r;
	que[wp].c = c;
	que[wp].time = time;
	wp++;
}
NODE Out_Que() {
	return que[rp++];
}
int BFS(void) {
	int dr[4] = { -1,1,0,0 }, dc[4] = { 0,0,-1,1 }; //상하좌우
	int i, j, nr, nc;
	int max = -1;
	NODE q;
	In_Que(sr, sc, 0);
	visit[sr][sc] = 1; // 방문체크
	while (rp < wp) { // 큐 empty check
		//q = que[rp++];
		q = Out_Que(); // 현재 좌표
		//if (q.r == er && q.c == ec) return q.time;
		for (i = 0; i < 4; i++) {
			nr = q.r + dr[i];
			nc = q.c + dc[i];
			if (nr<1 || nr>R || nc<1 || nc>C) continue; // 범위 벗어나면 스킵
			if (visit[nr][nc] == 1) continue;
			if (map[nr][nc] == 1) { //연결점 찾기(길)
				In_Que(nr, nc, q.time + 1);
				visit[nr][nc] = 1;
				ju[nr][nc] = q.time + 1;
			}
		}
	}
	//가장 큰 값을 return;
	for (i = 1; i <= R; i++) {
		for (j = 1; j <= C; j++) {
			if (max < ju[i][j]) {
				max = ju[i][j];
			}
		}
	}
	return max;
	//return -1; //큐가 빈상태(예외체크 - 미로탈출의 경우 예외경우 없음)
}
void input(void) {
	int i, j;
	scanf("%d %d", &C, &R);
	for (i = 1; i <= R; i++) {
		for (j = 1; j <= C; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	scanf("%d %d", &sc, &sr);
}

int find_service() {
	int i, j, cnt = 0;
	for (i = 1; i <= R; i++) {
		for (j = 1; j <= C; j++) {
			if (map[i][j] == 1 && visit[i][j] == 0) {
				cnt++;
			}
		}
	}
	return cnt;
}
int main(void) {
	int sol, sol2;
	input();
	sol = BFS();
	sol2 = find_service();
	printf("%d\n", sol + 3);
	printf("%d\n", sol2);
	return 0;
}

:BFS를 돌면서 map에 cnt++ 값을 기록 해준다. 그 후 map에서 가장 큰 수에 +3 을 더하면 저글링이 마지막으로 죽는 시간이 된다. 다시 map을 돌며 저글링이지만 방문한적이 없는 저글링 수를 카운트 한다.