백준 2178번 C++

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

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int N,M;
int arr[101][101]; //미로
int visit[101][101]; //방문

int dy[] = {-1,0,1,0}; // 좌표 이동 값 (상, 우, 하, 좌)
int dx[] = {0,1,0,-1}; 

void BFS(int n, int m)
{
    visit[n][m]=1; // 방문 표시
    queue<pair<int, int>> q; // 큐를 생성
    q.push(make_pair(n,m)); // 시작 점 큐에 추가 

    while (!q.empty()) // 큐가 비어있을 때 까지
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop(); // 큐의 맨 앞 데이터 제거

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < N && ny >=0 && ny < M) // 미로의 범위를 벗어날 떄
            {
                //길이 있고 && 방문했던 적이 없는 경우
                if(arr[nx][ny] == 1 && visit[nx][ny] == 0)
                {
                    visit[nx][ny] = visit[x][y] +1; // 최단거리 업데이트
                    q.push(make_pair(nx,ny)); // 큐에 추가
                }
            }
        }
    }
}

int main()
{   
    cin>>N>>M;
    for(int i = 0; i<N ; i++){
        for(int n=0 ; n<M ; n++){
            char ch;
            cin >> ch;
            arr[i][n] = ch - '0';
            //아니면 scanf("%1d", &arr[i][n]); 이거 써도 가능
        }
    }
    memset(visit, 0, sizeof(visit)); // reset
    BFS(0,0);
    cout<<visit[N-1][M-1]; // 도착점까지의 최단 거리 출력
}

하다가 포기

할 뻔 했지만~

 

dfs / 큐 사용

 

상, 하, 좌, 우 4방향을 모두 확인하여 각 위치로 이동이 가능한지의 여부를 파악하는 것이 BFS 알고리즘에서 미로 탐색의 핵심, 이 문제가 어렵다면 이동 알고리즘 찾아보기!

 

공부하면서 참고한 글 : https://seminzzang.tistory.com/97

간단한 이동 알고리즘 설명

이 미로 문제에서는 상, 하, 좌, 우로만 이동할 수 있으며, 각 이동 방향에 대한 좌표 변화를 다음과 같이 dx와 dy 배열로 정의한다.

int dy[] = {-1,0,1,0}; // 좌표 이동 값 (상, 우, 하, 좌)
int dx[] = {0,1,0,-1};

 

현재 위치 (x, y)에서 다음 위치를 (nx, ny)라고 할 때, 위에서 아래로 이동하는 경우에는 (nx, ny) = (x + dx[2], y + dy[2])로 이동한다. 반복문을 사용하여 상, 하, 좌, 우 4방향을 모두 탐색하며 각 위치를 방문하는 것이므로 for 반복문을 4번 돌린다. 4방향을 모두 확인하여 각 위치로 이동이 가능한지 여부를 파악하는 것이 BFS 알고리즘에서 미로 탐색의 핵심이다.

 

문제 푸는 포인트

• 붙어있는 수 입력 받기

1. scanf 사용 - %숫자d, 숫자에 받아오고 싶은 글자 개수 입력!

scanf("%1d", &arr[i][n]);

2. 문자로 숫자를 한 개씩 입력받아서 숫자로 변환해주기 - 숫자니까 받아온 문자 - 0

char ch;
cin >> ch;
arr[i][n] = ch - '0';