옌의 로그

문제[백준] 쉬운 최단거리  사용 알고리즘- BFS (너비우선탐색)해결방법목표지점을 시작점으로 생각하고, BFS 탐색을 하면서 visited 배열에 이동거리를 갱신해준다탐색종료 후, 갈 수 있는 지점이나, 도달하지 못한 케이스를 찾아 visited 배열을 -1로 바꿔준다소스코드사용언어 : c++#include #include using namespace std;int N, M;int start_x, start_y;int map[1001][1001];int visited[1001][1001];int dir[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}}; //위, 좌, 하, 우void bfs(int y, int x){ queue> q; q.push(make_pair(y, x..

문제 [프로그래머스] 게임 맵 최단거리 사용 알고리즘 - 너비우선탐색 (Breath-First Search) 해결방법 BFS사용해서 풀면 되는데, 결국 문제에서 구해야 하는 것은 최단 경로로 이동했을 때의 길이이므로, 방문을 체크하는 visited 배열에 길이를 저장해주도록 한다 그래프에서 상,하,좌,우 로 이동이 가능하므로 4방향 이동을 간단하게 표현하기 위해 dir 배열을 만들어 사용 needVisit배열이 BFS의 큐로 보면 되고, 이때 FIFO이므로 while 루프에서 꺼낼 때 shift() 메소드를 사용해 먼저 들어온 것 부터 체크 방문하지 않은 지점 (visited배열의 값이 0) 혹은, 이미 방문한 지점이지만 현재 위치에서 한 칸 이동한 것의 길이가 더 최단일 경우 큐(needVisit)에 ..