문제
문제 설명
N×M크기의 배열로 표현되는 미로가 있다.
ex)
1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.
한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
문제분석
일단 이문제는 BFS로 분류되어있는 문제로 BFS를 사용하여 해결을 해야하는 문제이다.
이 문제에서 구해야하는 것을 미로의 1,1에서 시작하여 N,M까지 이동하는데 지나가야하는 최소 칸수를 구하는 것이 목표이다.
BFS(너비 우선 탐색)
BFS는 그래프 자료구조의 탐색 방법중 하나로 시작 정점과 가까운 정점부터 탐색하는 방법이다.
이 방법의 사용을 위해서는 가까운 정점들을 차례로 저장하고 꺼낼 수 있는 큐가 필요하다.알고리즘은 큐에서 정점을 꺼내어 방문하고 인접한 정점들 중 방문하지 않은 정점을 큐에 추가하며
이 과정을 큐가 비어있을때까지 반복한다-C언어로 쉽게 풀어쓴 자료구조
BFS의 방법을 시뮬레이션을 통해서 확인하고 싶다면 아래 링크에서 확인이 가능하다.
시뮬레이션
해결 방법
먼저 시작점인 1,1을 큐에 삽입한다. 그 후에 큐에서 pop한 칸으로 이동하여 해당 칸에서 이동이 가능하며 방문하지 않은 칸을 큐에 push하고 지나온 칸수는 현재칸의 지나온 칸수+1을 넣어주면 된다. 동일한 과정을 반복하고 이 과정을 큐가 빌때까지 반복하면 된다.
코드
#include<iostream>
#include<vector>
#include<string>
using namespace std;
void push(vector<vector<int>>& q, int a, int b)
{
q.push_back({ a,b });
}
vector<int> pop(vector<vector<int>>&q) {
vector<int> ret = q[0];
q.erase(q.begin());
return ret;
}
int valid(vector<vector<int>>v, int a, int b)
{
if (a < 0 || a >= v.size()) return 0;
if (b < 0 || b >= v[0].size()) return 0;
if (v[a][b] == 0) return 0;
return 1;
}
int bfs(vector<vector<int>>v, vector<vector<int>> &visit, vector<vector<int>> &q)
{
int move[4] = { -1,1,0,0 };
int n = v.size();
int m = v[0].size();
vector<int> val;
int x, y, nx, ny;
while (q.size() != 0)
{
val = pop(q);
x = val[0];
y = val[1];
for (int i = 0; i < 4; i++)
{
nx = x + move[i];
ny = y + move[3 - i];
if (valid(v, nx, ny) == 1)
{
if (visit[nx][ny] == 0) {
push(q, nx, ny);
visit[nx][ny] = visit[x][y] + 1;
}
}
}
}
return visit[n-1][m-1];
}
int main() {
int n, m, answer = 0;
cin >> n >> m;
vector<vector<int>> v(n, vector<int>(m,0));
vector<vector<int>> visit(n, vector<int>(m,0));
vector <vector<int>>q;
char c;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> c;
v[i][j] = c-'0';
}
}
q.push_back({0,0});
visit[0][0] = 1;
cout << bfs(v, visit, q);
}
+맞긴 했지만 시간이 너무 오래걸린다.
왜 그런지 찾아보니 벡터를 이용할때 배열보다 걸리는 시간이 더길다고 한다.
참고링크
해당부분을 참고하여 큐를 제외하고 v,visit부분들을 배열로 변경해 보았다.
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int v[100][100] = { 0 };
int visit[100][100] = { 0 };
void push(vector<vector<int>>& q, int a, int b)
{
q.push_back({ a,b });
}
vector<int> pop(vector<vector<int>>&q) {
vector<int> ret = q[0];
q.erase(q.begin());
return ret;
}
int valid(int n,int m,int a, int b)
{
if (a < 0 || a >= n) return 0;
if (b < 0 || b >= m) return 0;
if (v[a][b] == 0) return 0;
return 1;
}
int bfs(int n,int m,vector<vector<int>> &q)
{
int movex[4] = { -1,1,0,0 };
int movey[4]={0,0,-1,1};
vector<int> val;
int x, y, nx, ny;
while (q.size() != 0)
{
val = pop(q);
x = val[0];
y = val[1];
for (int i = 0; i < 4; i++)
{
nx = x + movex[i];
ny = y + movey[i];
if (valid(n,m, nx, ny) == 1)
{
if (visit[nx][ny] == 0) {
push(q, nx, ny);
visit[nx][ny] = visit[x][y] + 1;
}
}
}
}
return visit[n-1][m-1];
}
int main() {
int n, m;
cin >> n >> m;
vector <vector<int>>q;
char c;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> c;
v[i][j] = c-'0';
}
}
q.push_back({0,0});
visit[0][0] = 1;
cout << bfs(n, m, q);
}
시간이 크게 감소한것을 확인할 수 있다.
v.data()를 이용하면 포인터를 이용하여 접근하기에 시간이 단축된다고도 되어있는데 1차원 벡터에서만 적용이 가능한것 같아 사용하지는 못했다.
대부분의 문제에서 벡터를 사용하였는데 이렇게 시간차이가 많이 나는 것을 보니 벡터만 사용하면 안될듯하다.
