[Programmers]게임 맵 최단거리

스스로 BFS,DFS가 부족하다고 생각해서 선택한 문제

문제 풀이에 앞서 DFS와 BFS를 비교해보자면

DFS: 깊이 우선 탐색(DFS, Depth-First Search)

• 루트노드(혹은 특정노드)에서부터 모든 노드를 완벽하게 탐색하는 방법
• 재귀 용법 또는 스택을 사용하고 어떤 노드를 방문했는지에 대한 여부를 반드시 검사해야한다.
• BFS보다는 간단하지만 느리다. 그러나 해가 없는 경로가 깊을 경우 시간이 오래걸릴 수 있고, 얻어진 해가 최단 경로가 된다는 보장이 없다.
• 인접 행렬, 인접 리스트냐에 따라 구현 방법이 다르다.
  *인접 리스트로 DFS 구현 시 시간 복잡도는 O(N+e)이고, 인접 행렬로 DFS 구현 시 시간 복잡도는 O(N^2)이다.

BFS: 너비 우선 탐색(BFS, Breadth-First Search)

• 루트노드(혹은 특정노드)부터 시작해서 인접한 노드들을 탐색해나가는 방식
• 가중치가 동일한 조건에서의 최단 경로 또는 임의의 경로를 찾을 때 이 알고리즘을 선택한다.
• DFS보다는 저장공간이 보다 더 필요하다.
• 선입선출(First In First Out) 원칙의 자료구조인 Queue를 사용한다.
• 재귀법으로 동작하지 않아서 어떤 노드를 방문했는지에 대한 여부를 반드시 검사해야한다.
  *인접 리스트로 DFS 구현 시 시간 복잡도는 O(N+e)이고, 인접 행렬로 DFS 구현 시 시간 복잡도는 O(N^2)이다.

1. queue에 x,y좌표를 넣을 수 있는 Struct를 만들고 queue[0]에 루트노드를 삽입(enqueue)한 후 방문한 노드를 체크한다.

• int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};를 선언하여 4방으로 움직일 수 있게 한다.

2. queue에서 꺼낸 노드와 인접한 노드들을 dir배열을 이용하여 방문한다.

• 꺼낸 노드와 인접한 노드가 없다면 queue의 앞에서 노드를 꺼낸다.(dequeue)
• 방문된 노드를 삽입하고 체크한다.
• maps에 이동한 누적 거리를 더해준다.

3. queue가 전부 소진될 때까지 반복한다. (head != tail)

• 목적지에 도달했다면 목적지의 maps 값을 리턴
• 이 문제에선 큐가 전부 소진되었다면 목적지에 도달하지 못하였다는 뜻이므로 -1 리턴

정답코드

#include<vector>
using namespace std;


int solution(vector<vector<int> > maps)
{
    struct Node{int y,x ;} queue[10000];
    int visited[100][100] = {0,};
    int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};

    int head,tail =1;
    int l = maps.size();
    int w = maps[0].size();
    
    queue[0]={0,0};
    visited[0][0]=1;
    while(head!=tail){
        Node now = queue[head];
        
        for(int i = 0 ; i < 4 ; i++){
            int dy = dir[i][0]+ now.y;
            int dx = dir[i][1]+ now.x;
            
            if(dy < 0 || dx < 0 || dy >=l || dx >= w) continue;
            if(maps[dy][dx] == 0 || visited[dy][dx]==1) continue;
            
            visited[dy][dx]=1;
            
            maps[dy][dx] = maps[now.y][now.x] + 1;
            queue[tail++] = {dy,dx};
            
            if(dy==l-1 &&dx == w-1)return maps[dy][dx];
        }
        head++;
    }
    
    return -1;
}

처음에는 새로 정의할 함수에서 처리하기 위해 struct인 Node와 visited 2차원 배열을 전역변수로 남겨 놓았었는데 이 때문에 효율성 테스트에서 감점을 받았다.

->불필요한 전역변수를 지역변수로 옮기니 통과했다.