c언어 2589번 보물섬 (백준)

#include <stdio.h>

typedef struct N {
	int x, y, z;	
}N;

int main(void) {
	int V[4] = {-1, 0, 1, 0};
	int H[4] = {0, 1, 0, -1};
	int n, m, ans=0;
	scanf("%d %d", &n, &m);
	
	int map[n][m];
	
	for(int i=0; i<n; i++) { //map 입력 받기
		char str[m];
		scanf("%s", str);
		for(int j=0; j<m; j++) {
			map[i][j] = str[j];
		}
	}
	
	int head = 0, tail = 0; //요소가 나올 인덱스, 요소가 들어갈 인덱스
	N q[2600]; //크게 잡아줍니다. 큐
	
	for(int i=0; i<n; i++) { //각각의 위치에서
		for(int j=0; j<m; j++) {
			if(map[i][j] == 'L') { //땅 일 경우 BFS
                head = tail = 0;
				N tmp = {i, j, 0};
				char v[50][50]={}; //방문확인을 위한 배열
				v[i][j]=1; //처음 위치를 방문 처리
				q[tail++] = tmp; //큐에 삽입
				while(head < tail) { //BFS
					int x = q[head].x;
					int y = q[head].y;
					int z = q[head].z;
					++head;
					
					ans = (ans > z) ? ans : z;
					z++;
					
					for(int k=0; k<4; k++) {
						x += V[k];
						y += H[k];
						if(x>=0 && y>=0 && x<n && y<m && map[x][y] == 'L' && v[x][y]==0) {
							v[x][y] = 1;
							N tmp2 = {x, y, z};
							q[tail++] = tmp2;
						}
						x -= V[k];
						y -= H[k];
					}
				}
			}
		}
	} printf("%d", ans);
}

풀이 : BFS (DFS로도 가능합니다)

 

크기가 50x50 이 한계이다보니 BFS을 위한 큐를 포인터를 이용하지 않고 배열 큐만으로도 가능합니다.

 

https://www.acmicpc.net/problem/2589

2589번: 보물섬