미로 최단거리 BFS 활용

#include <bits/stdc++.h>
using namespace std;

struct Node{
	int row, col;
	Node(int a, int b){
		row=a;
		col=b;
	}
	
};

int arr[7][7];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	queue<Node> Q;

	for(int i=0; i<7; i++){
		for(int j=0; j<7; j++){
			scanf("%d",&arr[i][j]);
			if(arr[i][j]==1) arr[i][j] = -1;
		}
	}
	arr[0][0] = 1;
	Q.push(Node(0,0));
	while(!Q.empty()){
		int x = Q.front().row;
		int y = Q.front().col;
		Q.pop();
		
		if(x==6 && y==6) break;
		
		
		for(int i=0; i<4; i++){
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx<0||nx>6||ny<0||ny>6) continue;
			if(arr[nx][ny]==-1 || arr[nx][ny]>0) continue;
			
			arr[nx][ny] = arr[x][y]+1;
			Q.push(Node(nx,ny));
		}
	}
	
	printf("%d",arr[6][6]-1);
}

장애물을 -1로 두고

 

거리를 양수로 표기하면서 BFS를 돌면 편하다.

 

첫 시작점도 방문했다는걸 표기하기 위해 1로 둔다.

 

나중에 답을 구할 땐 1을 다시 빼준다.