[c++] 섬나라 아일랜드, 미로의 최단거리통로(BFS)

섬나라 아일랜드

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <queue>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int map[30][30];
struct Loc {
	int x;
	int y;
	Loc(int a, int b){
		x = a;
		y = b;		
	}
};
queue<Loc> Q;
int main() {
	int n, k, cnt=0;
	//freopen("input.txt", "rt", stdin);
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			scanf("%d", &map[i][j]);
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(map[i][j]==1){
				Q.push(Loc(i, j));
				map[i][j]=0;
				while(!Q.empty()){
					Loc loc =Q.front();
					Q.pop();
					for(k=0; k<8; k++){
						int xx = loc.x + dx[k];
						int yy = loc.y + dy[k];
						if(map[xx][yy]==1){
							Q.push(Loc(xx, yy));
							map[xx][yy]=0;
						}
					}
				}
				cnt++;
			}
		}
	}
	printf("%d\n", cnt);
	return 0;
}

 

미로의 최단거리통로

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <queue>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int map[30][30], min_val=2147000000;
struct Loc {
	int x;
	int y;
	Loc(int a, int b){
		x = a;
		y = b;		
	}
};
queue<Loc> Q;
int main() {
	int n, k, cnt=0, res;
	freopen("input.txt", "rt", stdin);
	for(int i=1; i<=7; i++){
		for(int j=1; j<=7; j++){
			scanf("%d", &map[i][j]);
		}
	}
	Q.push(Loc(1, 1));
	map[1][1]=0;
	cnt=0;
	while(!Q.empty()){
		Loc loc =Q.front();
		Q.pop();
		for(k=0; k<4; k++){
			int xx = loc.x + dx[k];
			int yy = loc.y + dy[k];
			if(map[xx][yy]==0 && xx<=7 && xx>=1 && yy<=7 && yy>=1){
				//printf("xx: %d, yy: %d\n", xx, yy);
				Q.push(Loc(xx, yy));
				map[xx][yy]=map[loc.x][loc.y]+1;
			} 
		}
	}
	printf("%d\n", map[7][7]);
	return 0;
}