목차
2178. BFS
https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net


[풀이]
각행의 수들은 붙어서 입력이 들어온다. 이러한 경우 이중 for문을 통해 입력받는 방법을 코드로 확인할 수 있다.
2차원 배열 board을 선언할 때부터 문자열의 배열로 선언할 수도 있지만 더욱 실수할 확률이 높다.
뿐만 아니라 각 칸의 dist 배열을 2차원으로 초기화하는데 이중 for문이 필요하기 때문에 같이 사용하면 된다.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[502][502];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int dist[502][502];
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i=0; i<n; i++){
string tmp; cin >> tmp;
for (int j=0; j<m; j++) {
board[i][j] = tmp[j] - '0';
dist[i][j] = -1;
}
}
queue<pair<int, int>> Q;
Q.push({0,0});
dist[0][0] = 0;
while(Q.size()){
pair<int,int> cur = Q.front(); Q.pop();
for (int dir=0; dir<4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx >= n || nx < 0 || ny >= m || nx < 0) continue;
if (dist[nx][ny]!=-1 || board[nx][ny]==0) continue;
Q.push({nx,ny});
dist[nx][ny] = dist[cur.X][cur.Y] + 1;
}
}
cout << dist[n-1][m-1]+1;
}
'PS' 카테고리의 다른 글
BOJ - 1260. DFS와 BFS (C++) (0) | 2024.03.19 |
---|---|
BOJ - 1697. 숨바꼭질 (C++) (0) | 2024.03.18 |
BOJ - 1620. 나는야 포켓몬 마스터 이다솜 (C++) (0) | 2024.03.14 |
PS (0) | 2024.03.13 |
BOJ - 2493. 탑 (C++) (0) | 2024.03.12 |
2178. BFS
https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net


[풀이]
각행의 수들은 붙어서 입력이 들어온다. 이러한 경우 이중 for문을 통해 입력받는 방법을 코드로 확인할 수 있다.
2차원 배열 board을 선언할 때부터 문자열의 배열로 선언할 수도 있지만 더욱 실수할 확률이 높다.
뿐만 아니라 각 칸의 dist 배열을 2차원으로 초기화하는데 이중 for문이 필요하기 때문에 같이 사용하면 된다.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[502][502];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int dist[502][502];
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i=0; i<n; i++){
string tmp; cin >> tmp;
for (int j=0; j<m; j++) {
board[i][j] = tmp[j] - '0';
dist[i][j] = -1;
}
}
queue<pair<int, int>> Q;
Q.push({0,0});
dist[0][0] = 0;
while(Q.size()){
pair<int,int> cur = Q.front(); Q.pop();
for (int dir=0; dir<4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx >= n || nx < 0 || ny >= m || nx < 0) continue;
if (dist[nx][ny]!=-1 || board[nx][ny]==0) continue;
Q.push({nx,ny});
dist[nx][ny] = dist[cur.X][cur.Y] + 1;
}
}
cout << dist[n-1][m-1]+1;
}
'PS' 카테고리의 다른 글
BOJ - 1260. DFS와 BFS (C++) (0) | 2024.03.19 |
---|---|
BOJ - 1697. 숨바꼭질 (C++) (0) | 2024.03.18 |
BOJ - 1620. 나는야 포켓몬 마스터 이다솜 (C++) (0) | 2024.03.14 |
PS (0) | 2024.03.13 |
BOJ - 2493. 탑 (C++) (0) | 2024.03.12 |