C# 게임 맵 최단거리 - BFS 길찾기 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/1844

 

 

나의 풀이

using System;
using System.Collections.Generic;

class Solution { // 최단거리는 BFS가 유리.
    public int solution(int[,] maps) {
        
        int w = maps.GetLength(0);
        int h = maps.GetLength(1);
        
        var open = new Queue<(int x, int y)>();
        var parents = new Dictionary<(int x, int y), (int x, int y)>(); 
        var dirs = new (int x, int y)[4]{(-1, 0), (1, 0), (0, -1), (0, 1)};
        
        open.Enqueue((0, 0));
        maps[0, 0] = 0;
        bool found = false;
        
        while(open.Count > 0)
        {
            (int x, int y) cur = open.Dequeue();
            if(cur.x == w - 1 && cur.y == h - 1) // 도달!
            {
                found = true;
                break;
            }
            
            foreach((int x, int y) dir in dirs)
            {
                (int x, int y) p = (cur.x + dir.x, cur.y + dir.y);
                
                if(p.x < 0 || p.x >= w || p.y < 0 || p.y >= h)
                    continue;
                
                if(maps[p.x, p.y] != 1)
                    continue;
                
                parents[p] = cur;
                open.Enqueue(p);
                maps[p.x, p.y] = 0;
            }
        }
        
        if(found)
        {
            int length = 0;
            (int x, int y) cur = parents[(w - 1, h - 1)];
            while(!(cur.x == 0 && cur.y == 0))
            {
                cur = parents[cur];
                length++;
            }
            length += 2; // 시작과 끝 더함
            return length;
        }
        else
        {
            return -1;
        }
    }
}

DFS는 완전탐색이기 때문에 수행시간 초과가 나오고

BFS는 찾으면 바로 종료되기 때문에 DFS보다는 BFS를 사용하는게 맞다고 한다.

 

중요한점!

visited 체크를 Enqueue하면서가 아니라 Dequeue하면서 호출할 경우

중복으로 방문하는 하게 되므로 효율성 테스트에서 실패한다.

 

 

다른사람풀이 1

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;

class Solution 
{
    public int[] dir_x ={0,0,-1,1};
    public int[] dir_y = {-1,1,0,0};
    public int solution(int[,] maps)
    {
        var st = new Tuple<int,int>(0,0);
        var end = new Tuple<int,int>(maps.GetLength(0) - 1,maps.GetLength(1) - 1);
        int[,] visit = new int[maps.GetLength(0), maps.GetLength(1)];
        var que = new Queue<Tuple<int,int>>();
        que.Enqueue(st);
        visit[st.Item1, st.Item2] = 1;
        while(que.Count != 0)
        {
            var now = que.Dequeue();
            for(int lp = 0; lp < 4; lp++)
            {
                int yy = now.Item1 + dir_y[lp];
                int xx = now.Item2 + dir_x[lp];
                if(xx < 0 || yy < 0 || yy >= maps.GetLength(0) || xx >= maps.GetLength(1)) continue;
                if(visit[yy,xx] == 0 && maps[yy,xx] == 1)
                {
                    que.Enqueue(new Tuple<int,int> (yy,xx));
                    visit[yy,xx] = visit[now.Item1, now.Item2] + 1;
                }
            }
        }
        if(visit[end.Item1, end.Item2] == 0) return -1;
        else
            return visit[end.Item1, end.Item2];
    }
}

코드가 비교적 짧다.

 

 

다른사람풀이 2

using System;
using System.Collections.Generic;

class Solution {
    int n = 0;
    int m = 0;
    int[] dx = { -1, 1, 0, 0 };
    int[] dy = { 0, 0, -1, 1 };
    Queue<(int, int)> que = new Queue<(int, int)>();

    public void bfs(int i,int j,int[,] arr)
    {
        que.Enqueue((i, j));
        while (que.Count != 0)
        {
            (int a, int b) = que.Dequeue();
            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k];
                int y = b + dy[k];
                if ((0<= x&& x< n)&& (0<=y&&y<m)&&(arr[x,y] == 1))
                {
                    que.Enqueue((x, y));
                    arr[x, y] = arr[a, b] + 1;
                }
            }
        }
    }
    public int solution(int[,] arr)
    {
        n = arr.GetLength(0);
        m = arr.GetLength(1);

        bfs(0, 0,arr);

        if (arr[n-1,m-1] == 1)
            return -1;
        else
            return (arr[n - 1, m - 1]);
    }
}

arr에 거리를 직접 기록해가면서 체크한 부분이 인상적.