백준 2178, 최단거리 BFS 문제 (+ 공백없이 숫자를 입력받는 법)

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

2178번: 미로 탐색

해당 문제는 맵이 주어지고, 맵의 처음부터 맨 끝 지점까지 최단거리를 구하는 문제이다.

Key Point

1. 맵이 주어져 있다. -> 2차원 배열을 통해 맵을 구현하고, ny[] / nx[]를 사용한다.
2. 그래프의 노드 간 가중치가 모두 동일한 최단거리 문제이다. -> BFS를 사용한 최단거리 알고리즘을 사용한다.

숫자를 공백없이 입력받는 법

1. String 문자열을 사용

cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> s;
		for(int j = 0; j < m; j++){
			arr[i][j] = s[j] - '0';
		}
	}

C++의 문자열은 인덱스를 통해 문자 하나하나에 접근이 가능하다. 따라서 공백없이 한 줄을 문자열로 받은 다음에 각각의 문자에 대해 '0'을 빼서 문자를 숫자로 변환한다. (cin은 개행문자(띄어쓰기, 한줄띄기)까지 받는다.)

 

2. scanf 사용

cin >> n >> m;
for(int i = 0; i < n; i++){
	for(int j = 0; j < m; j++){
    	scanf("%1d", &arr[i][j]);
    }
}

scanf를 사용하면 앞에 형식을 지정할 수 있다. 따라서 숫자를 입력받는 경우 "%d"를 사용하며, 앞에 1을 붙이게 되면 숫자 한 자리씩 받을 수 있다.

 

만약, 숫자가 아닌 문자를 입력받을 때는 cin을 사용해야 한다.

for(int i = 0; i < 2; i++){
	for(int j = 0; j < 4; j++){
    	scanf("%c", &arr[i][j]);
    }
}

%c로 입력을 받게 되면, 특수문자 및 엔터를 문자로 취급하기 때문에 입력받은 값이 제대로 들어가지 않는다.

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

char a[10][10];

int main(){
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 4; j++){
			cin >> a[i][j];
		}
	}
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 4; j++){
			cout << a[i][j] << " ";
		}
		cout << '\n';
	}
	
	return 0;
}

cin의 경우, 숫자를 입력받을 때는 개행문자까지 입력을 받지만 문자를 입력받을 때는 문자 한 개밖에 입력을 못받는다.

문제 코드

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

int n, m, a, b, ny, nx;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int arr[101][101];
int visited[101][101];

queue<pair<int, int>> q;
string s;

void bfs(int y, int x){
	visited[y][x] = 1;
	q.push({y,x});
	
	while(q.size()){
		
		tie(y,x) = q.front(); q.pop();
		for(int i = 0; i < 4; i++){
			ny = y + dy[i];
			nx = x + dx[i];
			if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			if(arr[ny][nx] == 0 || visited[ny][nx]) continue;
			
			q.push({ny,nx});
			visited[ny][nx] = visited[y][x] + 1;
		}
	}
}

int main(){
	
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> s;
		for(int j = 0; j < m; j++){
			arr[i][j] = s[j] - '0';
		}
	}
	
	bfs(0,0);
	
	cout << visited[n-1][m-1];
	
	return 0;
}

• BFS 문제의 경우, Queue를 활용해야 한다.
  • 방문을 했을 경우, Queue에 Push해야 한다.
  • 주변 노드를 탐색해야하는 경우, Queue에서 Pop해야 한다.
• 맵을 활용한 문제를 풀 경우, 반드시 첫 if문은 배열 인덱스의 오버/언더 플로우를 탐색하는 조건문이어야 한다.

 

https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의