백준 15591←클릭 간선의 갯수가 N-1개 이므로 특정 지점에서 출발하였을 경우 다른 노드를 2번 방문할 일은 없다. 고로 단순 BFS로 구현 가능하다. 아이디어 > BFS를 통해 mid를 계속 갱신한다. mindiststart = min(mindiststart, dist); 여기서 dist는 mid와 end사이의 거리이다. 코드 github

백준 9376←클릭 아이디어 >* 죄수 2명과 상근이의 위치를 기준으로 다익스트라를 적용하여 지도의 각 위치까지의 최소 거리를 모두 구한다. >* 지도의 특정 위치에서 세 최소 거리의 합은 해당 위치까지 상근이와 죄수 2명이 최소 거리로 이동했을 때 드는 비용이다. >* 특정 위치에 문이 있을 경우 2를 빼주는데 이는 단순이 합을 구하게 되면 해당 위치에서 문을 3번 열기 때문이다. >* 가장 비용이 적게 드는 값을 찾는다. 변수 설정 sx1, sy1, sx2, sy2 : 죄수의 위치 VertexInfo : 노드의 좌표와 시작 지점에서 해당 위치까지 가는

백준 12100←클릭 DFS를 이용하는 문제이다. 문제의 제한조건에서 DFS의 길이가 5층으로 제한되어 있기에 시간 복잡도는 크지 않다. DFS를 사용하는 것 보다 문제를 구현하는 것이 조금 귀찮은 문제다. 변수 설정 n: 현재 DFS의 층에 해당한다. d: 움직임의 종류이다. 0부터 3의 값을 가지며 각각 ←,→,↓,↑에 해당하는 연산이다. arr: 전체 2048배열을 저장한다. DFS이기 때문에 전역변수로 설정. move: bool 변수로 이번 연산에서 배열에 움직임이 있었으면 true 아니면 false이다. s: 스택의 개념으로 사용되는 변수로 어차피 하나의 수만 저장할 것이므로 int형으로 선언했다. zero: 배 층마다 움직임 연산을 하는데 해당 층에 0이 있으면 zero가 true가 되고 이후 숫자가 나오면 move가 true가

SWEA 1855 LCA알고리즘을 사용하여 최소공통 조상을 구하는 알고리즘이다. 처음에 LCA알고리즘을 몰라서 한칸씩 부모를 타고 올라가 시간 초과가 났던 문제이다. LCA란? 아이디어를 간단하게 요약하면 다음과 같다 >* 트리 구조체에서 자신의 2의 거듭제곱번째 조상을 dp배열에 저장한다. > > * 특정한 두 노드의 최소 공통 조상을 찾을 때 dp배열을 활용하여 1칸->2칸->4칸 ...씩 타고 올라간다. 일단 dp배열을 생성하는 코드는 다음과 같다 i 의 $$2^j$$번째 조상은 i의 $$2^j-1$$번째 조상의 $$2^j-1$$번째 조상이다 라고 이해하면 된다. 영준이가 방문할 노드는 BFS를 따라가기 때문에 Queue에 방문 순서를 넣어 이를 구현하였다

[SWEA 1249] (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD) 최저 비용으로 경로를 탐색하는 문제다. 문제의 조건을 2차원 배열 map으로 받았다. 또한, 특정 위치로 갈 때의 최소의 비용을 저장하는 2차원 배열을 cost로 하였다. 예) costi는 (i,j)로 가는 (지금 껏 계산한) 최소한의 비용이다. > cost는 지금 껏 계산한 비용보다 저렴한 비용으로 방문이 가능하면 해당 값으로 갱신한다. 갱신만 하면 끝이 아니다. 이 갱신으로 영향을 받을 수 있는 주변 좌표들 또한 재 갱신을 해야 하기에 해당 좌표를 다신 방문해야 하므로 다시 queue에 넣어야 한다. 코드 [깃허브](https://github.com/wonchul98/SWEA/blob/main/SWEAgithubu