2178 : 미로 탐색 - 붙어서 입력(scanf("%1d")), 2차원 배열, 방문배열, BFS, 방향벡터, pair,tie

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

2178번: 미로 탐색

문제요약

N*M 크기의 배열로 표현되는 미로.

(1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸의 수

 

난이도

Silver 1

---

풀이 포인트

 

• 너비우선탐색(BFS)
  • 한 정점에서 다른 정점으로의 최단 거리를 구할 때 적합.
  • queue의 선입선출 특성을 활용하여 인접한 것을 차례로 push, 먼저 들어온 것을 pop하는 로직으로 탐색!
• 2차원 좌표를 1차원 노드로 치환하여 생각하기.
  
  • pair<int, int> 
  • tie(int, int) 활용
• 입력이 붙어서 주어질 때
  • string으로 변환해서 받기
  • scanf로 ("%1d", &a)
  • char type으로 & cin

---

REVIEW

 

1차 시도

우선, 2차원 배열을 n,m 가변적으로 입력값을 받아 크기를 설정하려니,

지역변수로 선언해야해서 초기화를 시키는 방법을 고민하다, 쓰레기값이 들어가 원하는 값이 나오지 않았다.

 

그리고 입력값이 붙어서 들어온다는 것을 간과하고 cin으로 받았더니

입력받은 배열을 출력해보니 뒤에 자꾸 00과 000000 3줄이 더 붙는 걸 보게됌.

 

그래서 짠 코드를 실행해볼 수 조차 없었음..

 

2차 시도

단순히 오른쪽 이동이나, 아래쪽 이동이 가능하니?를 판단하여 이동하는 로직을 짰다.

하지만 예제를 몇 개 그려보니 위로 이동하는 방법도 필요하다는 걸 깨닫고

방문배열을 떠올렸다.

상하좌우 돌아가며 1인지를 검사하고 이동하고 좌표를 갱신하고, 이동 카운트를 세고, 방문했었는지를 체크하는 로직을 짜서,

겨우 성공은 했다.

 

모범 답안을 보니 BFS로 구현하는 것이더라.

BFS의 대표적 문제라고 하니 공부해두기.

---

CODE

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

const int max_n = 104;
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
int n,m,a[max_n][max_n], visited[max_n][max_n],y,x;

int main(){

    scanf("%d %d", &n, &m);

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

    queue<pair<int, int>> q;
    visited[0][0] = 1;
    q.push({0,0});

    while(q.size()){
        tie(y,x) = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny <0 || ny>=n||nx<0||nx>=m||a[ny][nx] == 0) continue;   //먼저 오버플로우부터 체크하고 들어가기.
            if(visited[ny][nx]) continue;

            visited[ny][nx] = visited[y][x] +1;
            q.push({ny,nx});
        }
    }

    printf("%d", visited[n-1][m-1]);
    return 0;

}