여느 날처럼 에줍사 스터디를 진행하다가 그래프 탐색 문제에 대해 논의를 하던 중 나머지 스터디원들은 BFS로 접근을 했지만, 혼자 다익스트라로 접근을 했던 적이 있습니다. "왜 다익스트라를 떠올렸을까?"라는 생각을 한 결과, 다음과 같은 잘못된 기저가 깔려있다는 것을 알 수 있었습니다.시간복잡도 : Dijkstra BFS 또한 완전탐색으로 최단 거리를 찾는데 시간이 오래 걸릴 것이라 생각함알고리즘 특성 차이이번 회고를 통해 아래와 같이 잘못된 정보들을 바로잡으려합니다.추상적인 시간복잡도두 알고리즘의 동작 방식조건에 따른 수행 방식 BFS와 Dijkstra에 대한 정리는 이전에 정리해 두었던 글이 있으니 참조용으로 링크만 올려두겠습니다.https://infinitecode.tistory.com/13 [알고..

문제 https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 풀이 3차원 방문체크를 활용한 Dijkstra 풀이 문제이해 문제를 읽고 예제를 보고 이해를 하려는데 개인적으로 상당히 난해했음. 일단 동작과정은 아래와 같음. #이라는 문에 대해서 어느 방향에서든 출발해도 상관없음. 빈칸 ‘.’에 대해 진행방향 그대로 직진만 가능. ‘!’ 칸은 거울 설치 가능한 곳으로써 해당 자리에 거울을 45도 설치 가능. 거울을 설치하게 되면 빛은 직진이 ..

문제 https://www.acmicpc.net/problem/30894 30894번: 유령의 집 탈출하기 첫째 줄에 유령의 집의 크기 $N, M$이 주어집니다.$(2≤N,M≤200)$ 둘째 줄에 유령의 집의 입구 좌표 $S_x, S_y$, 출구 좌표 $E_x, E_y$가 주어집니다.$(1≤S_x, E_x≤N, 1≤S_y, E_y≤M)$ 좌표 $(x, y)$는 위에서부터 www.acmicpc.net 풀이 3차원 방문체크를 활용한 BFS 풀이 접근법 3차원 방문배열을 활용 각 유령들은 시간에 따라 바라보는 방향이 바뀌는데 총 4가지의 서로 다른 맵이 존재함. 이 점을 활용하여 3차원 방문배열을 통해 각 방문배열마다 유령이 바라볼 수 있는 공간들에 대해 미리 전처리한 후 BFS 탐색을 수행. 소스코드 imp..

문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 DP를 활용한 완전탐색 첫번째 접근법 (BFS) 각 격자별로 BFS를 수행하면서 DP 메모이제이션을 수행. 다음 탐색좌표에 대한 최장길이 DP값이 있다면 해당 부분문제 해를 이용하여 현재 최장길이를 구하는 식으로 풀이. 두번째 접근법 (DFS) 첫번째 접근에서 메모리초과가 발생하여 DFS로 변경 로직자체는 동일 각 좌표마다 DFS를 수행하면서 다음 나아가는 좌표에 대해 메모이..