Scat

yongmin's dev blog

[BOJ] 9370번 미확인 도착지 - C++

"최단경로"

문제 미확인 도착지 풀이 다익스트라 응용 문제이다. 이 문제 역시, g, h를 지나면서 final 지점에 도착했을 때 가장 최소 비용으로 가는 경로를 확인하는 문제이다. 결과적으로, start -> g -> h -> final or start -> h -> g -> fianl 의 경로 중에 start --> f...

Posted by Yongmin on July 26, 2021

[BOJ] 1504번 특정한 최단경로 - C++

"최단경로"

문제 특정한 최단경로 풀이 다익스트라 알고리즘 응용문제이다. a, b 정점을 지나치면서 최종 지점까지 최소비용으로 도달하게 하는 문제이다. a, b 정점을 지나는 경로는 크게 두 가지가 있는데, 1->a->b->N, 1->b->a->N이 되겠다. 그래서 다익스트라 알고리즘으로 ‘1->a’, ‘a->b’, ...

Posted by Yongmin on July 25, 2021

[BOJ] 1753번 최단경로 - C++

"최단경로"

문제 최단경로 풀이 다익스트라 알고리즘에 배운 문제이다. 최소 비용을 구하는 알고리즘에는 크게 3가지 ‘다익스트라 알고리즘 : O(E * logN)’, ‘벨만-포드 알고리즘 : O(|V||E|)’, ‘ 플로이드 워샬 알고리즘 : O(V^3)’이 있다고 한다. 인접리스트에 pair로 push_back을 해주어, 간선이 이어진 부분과 value를 넣는...

Posted by Yongmin on July 25, 2021

[BOJ] 1707번 이분 그래프 - C++

"DFS와 BFS"

문제 이분 그래프 풀이 DFS, BFS를 이용한 문제이며, 이분 그래프에 대해서 알게된 문제이다. 이분 그래프는 연결된 점들이 각각 다른 색깔로 이루어진 그래프를 의미한다. 코드상, 계속해서 방문하며 색ㄱ랑르 번갈아가면서 입력을 해준다. 그 이후 확인작업을 통해 색깔이 같은 지점이 있다면 false, 그렇지 않다면 true를 출력하게 하여 이분 그래...

Posted by Yongmin on July 24, 2021

[BOJ] 7562번 나이트의 이동 - C++

"DFS와 BFS"

문제 나이트의 이동 풀이 BFS를 이용한 문제이다. 기본 코드에서 크게 다르지 않으며, 다만 이동 경로만 조건에 맞게 수정하면 된다. main의 For 문안에서 vector, queue 들이 선언이 계속 되기 때문에, 초기화 해주는 코드를 넣어주었다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19...

Posted by Yongmin on July 22, 2021

[BOJ] 2206번 벽 부수고 이동하기 - C++

"DFS와 BFS"

문제 벽 부수고 이동하기 풀이 BFS를 이용하여 풀이하는 문제이다. Reference를 참조하였다. 매 단계마다 4가지를 고려한다. 벽을 부쉈는지, 갈 장소가 0으로 되어 있는지, 1로 되어 있는지. queue 에는 (x,y) 좌표와 (벽을 부순 횟수, 경로의 cnt) 가 담겨있고, visit함수에는 x,y 좌표와 벽을 부순 횟수를 index로 삼는...

Posted by Yongmin on July 22, 2021

[BOJ] 1697번 숨바꼭질 - C++

"DFS와 BFS"

문제 숨바꼭질 풀이 큐를 이용해서 완전 탐색을 하는 코드이다. x-1, x+1, 2*x에 해당하는 값들을 queue에 넣고, 이미 넣었던 함수라면 어차피 반복되니 메모리를 사용하지 않기 위해 visit함수로 check를 해주면서 메모리를 절약해주었다. 완전탐색으로 원하는 값이 나올 때 depth를 출력하고 종료한다. 소스 코드 1 2 3 4 5 ...

Posted by Yongmin on July 21, 2021

[BOJ] 7576번 토마토 - C++

"DFS와 BFS"

문제 토마토 풀이 최소날짜를 구하는 문제로, BFS를 이용하여 풀이하였다. 처음 주어진 map에서 1인 지점의 좌표들을 먼저 넣음으로써 시작하였다. 그 이후, 상하좌우에 map이 0이며 방문하지 않으면 큐에 넣는 식을 반복하였다. -1의 경우는 미리 visit을 했다고 셋팅하여 -1을 밟지 못하게 만들어놨다. check함수를 이용하여, 마지막에 작성...

Posted by Yongmin on July 20, 2021

[BOJ] 2178번 미로 탐색 - C++

"DFS와 BFS"

문제 미로 탐색 풀이 DFS를 이용하여 코드를 작성하면, 완전 탐색을 통해 얻어낸 경로 중 최단값을 채택해야된다. 그로 인해 시간초과를 면할 수가 없다. 최단 거리 문제는 보통 BFS를 이용한다고 한다. BFS를 이용해서 상하좌우 근접해 있는 경로를 지날 때 마다 가중치 + 1을 하여 코드를 작성하면 최단경로를 효율적으로 만들 수 있다. 코드는 ...

Posted by Yongmin on July 19, 2021

[BOJ] 2667번 1로 만들기 - C++

"DFS와 BFS"

문제 단지번호붙이기 풀이 DFS로 코드를 작성하였다. 먼저 입력에서 숫자들이 “0110100” 이런식으로 띄어쓰기 없이 붙어서 입력으로 들어오는 것을 하나씩 받기 위해서 scanf("%1d", &map[i][j]); 로 받아들였다. 1d는 숫자들 한개씩을 입력으로 받아들이겠다는것이다. 그 이후 상하좌우를 의미하는 dx, dy함수를 기존의 d...

Posted by Yongmin on July 19, 2021

FEATURED TAGS
Format BOJ C++ Python Algorithm
ABOUT ME

짱구