[L2] 프로그래머스 게임 맵 최단거리 C++ 너비 우선 탐색, BFS

리뷰

프로그래머스

 

아주 기초적인 BFS 문제였다. 맵의 왼쪽 상단에서 오른쪽 하단으로 이동하고, 걸린 시간을 출력하는 문제

 

 

전역 변수

• dx, dy : 상하좌우 4방향으로 이동하기 위한 방향 배열
• v : BFS시 방문 처리 및 걸린 시간을 계산하기 위한 정수형 배열, 맵의 최대 크기인 100 * 100으로 초기화
• n, m : 맵의 행의 수 n, 맵의 열의 수 m
• Pos : BFS시 현재 위치 정보를 저장하기 위한 구조체

 

함수

1. bfs

int bfs(const vector<vector<int>>& maps)

 

맵을 탐색하며 우측 하단으로 갈 수 있는지 여부와, 걸리는 시간을 리턴하는 함수

1. 구조체 Pos타입의 큐 q를 초기화 하고 초기 위치 0, 0을 추가해 준다.
2. memset 메서드를 통해 방문 배열을 초기화 해주고, 초기위치에 방문 처리를 해준다.
3. 큐가 빌때까지 반복문을 수행하고, 4방향 탐색을 하며 모든 맵에 방문한다.
4. 단, 맵의 범위를 벗어나거나 이미 방문한 위치나 맵 상에서 벽에 막혀있는 경우는 이동하면 안된다.
5. 이동에 성공했을 경우 현재 위치의 방문 값 + 1을 이동 위치의 v배열에 최신화 해주고 좌표를 큐에 추가해 준다.
6. 만약 현재 위치가 우측 하단이라면 현재 위치의 방문값을 리턴해 준다.
7. 반복문이 끝날때 까지 목표 위치까지 도달하지 못했다면 -1을 리턴해 준다.

 

문제풀이

1. n, m을 맵의 행, 열의 개수로 초기화 해준다.
2. answer변수에 bfs함수의 리턴값을 저장해 준다. 매개변수로는 맵 정보를 전달한다.
3. answer를 리턴해 준다.

 

참고 사항

시뮬레이션을 돌려보니 시작 위치부터 거리가 1인 상태인 문제이다.

 

 

정답 코드

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

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int v[100][100];
int n, m;

struct Pos {
    int x, y;
};

int bfs(const vector<vector<int>>& maps) {
    queue<Pos> q;
    q.push({0, 0});
    memset(v, 0, sizeof(v));
    v[0][0] = 1;
    
    while(!q.empty()) {
        Pos pos = q.front(); q.pop();
        int cx = pos.x, cy = pos.y;
        if (cx == n - 1 && cy == m - 1) return v[cx][cy];
        
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i], ny = cy + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny] && maps[nx][ny]) {
                v[nx][ny] = v[cx][cy] + 1;
                q.push({nx, ny});
            }
        }
    }
    return -1;
}

int solution(vector<vector<int>> maps)
{
    n = maps.size();
    m = maps[0].size();
    int answer = bfs(maps);
    
    return answer;
}