인프런 커뮤니티 질문&답변

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

 

 

 

 

#include <bits/stdc++.h>

using namespace std;

int n, m;
int miro[101][101], visited[101][101];
int now_x=0, now_y=0, x, y;
int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	//input
	cin>>n>>m;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			scanf("%1d", &miro[i][j]);
		}
	}
	
	//bfs
	queue<pair<int, int>> q;
	visited[0][0]=1;
	q.push({0, 0}); //시작위치는 (0, 0)
	while(q.size()) {
		tie(y, x) = q.front();
		q.pop();
		
		for(int i=0; i<4; i++) { //동서남북에 1이 있는지 확인 
			int now_y = y+dy[i];
			int now_x = x+dx[i];
			
			if(now_y<0 || now_x<0 || now_y >=n || now_x>=m) { //미로 밖으로 벗어난 경우 건너뜀 
				continue;
			}
			if(miro[now_y][now_x]==0) { //0인 경우 건너뜀 
				continue;
			}
			if(visited[now_y][now_x]) { //이미 방문한 경우 건너뜀 
				continue;
			} 
			
			visited[now_y][now_x] = visited[y][x]+1; //전보다 depth가 하나 증가 
			q.push({now_y, now_x}); //같은 depth를 가지는 애들이 큐에 들어가게 됨 
		}
	}
	
	cout<<visited[n-1][m-1];
	
	return 0;
}