[백준 알고리즘] 2178번 미로찾기

이번에 풀어본 문제는 백준의 미로 찾기문제입니다.

2178번: 미로 탐색

문제는 정말로 미로찾기 문제이고, 주어진 미로에서 도착지까지 가는 최소 칸 수를 구하는 문제입니다.

처음엔 재귀함수로 풀었는데, 도착지가 있는 경우엔 재귀함수를 사용하는 것이 애매하더라구요. 그래서 queue로 접근해보았습니다!!

---

• 시작점(1,1)을 queue에 push한다.
• 현재 기준점을 기준(queue의 front)으로 위, 아래, 오른쪽, 왼쪽 4 방향을 검색한다.
• 끝

---

정말 전형적인 BFS, DFS문제입니다!!

제가 처음 문제를 풀었을 때는, 이렇게 풀었어요.

---

• 위와 동일
• queue에 집어넣는 것은 (x,y좌표와 (x,y)까지 가는 칸수)
• 도착지 까지 간 경우 기존 도착지 까지 간 칸수와 최근 들어온 칸수를 비교해서 작은 값으로 설정

---

이렇게 하니까 메모리 초과가 뜨더라구요..ㅠㅠ 역시 구조체의 단점 ㅠㅠ 그래서 다른 방법을 찾아보니까 방문했다는 것을 bool자료형이 아닌 int로 줘서 해당 값까지의 칸 수로 설정하는 방법을 선택했습니다!!

---

• queue에 집어 넣는 것은(x,y좌표)
• visit을 int형으로 설정해서 visit[x][y]의 값은 (1,1)에서 (x,y)까지 지나온 칸 수
• 마지막엔 도착지의 visit값을 반환

---

queue<DOT> que;
que.push({1,1});
while(!que.empty())
{
    int x = que.front().x;
    int y = que.front().y;
    que.pop();
    if(RightCheck(x,y))
    {
        visit[x][y+1] = visit[x][y]+1;
        que.push({x,y+1});
    }
    if(DownCheck(x,y))
    {
        visit[x+1][y] = visit[x][y]+1;
        que.push({x+1,y});
    }
    if(UpCheck(x,y))
    {
        visit[x-1][y] = visit[x][y]+1;
        que.push({x-1,y});
    }
    if(LeftCheck(x,y))
    {
        visit[x][y-1] = visit[x][y]+1;
        que.push({x,y-1});
    }
}
return visit[N][M];

코드에서 보면 다음 진입할 칸의 visit은 현재 기준 좌표의 visit값에서 1더한 값으로 설정해줘서 흩뿌려가는 방법..!!! 센스있는 풀이인 듯ㅎㅎ 다 끝나면 도착지의 visit값을 return!!! 간단하게 마무리가 되네요ㅎㅎ 

전체 코드는 여기있습니다! https://github.com/dinoHee/Baekjoon_Algorithm/blob/master/baekjoon%232178.cpp