BOJ
-
플로이드 워셜. BOJ 11404PS 2024. 7. 8. 17:49
https://www.acmicpc.net/problem/11404 바킹독님의 유튜브 (https://www.youtube.com/@BaaaaaaaaaaaaaaaaaaaaarkingDog)를 보며, 플로이드 워셜 알고리즘을 공부하고 있다. 바킹독 최고!https://blog.encrypted.gg/1035 [실전 알고리즘] 0x1C강 - 플로이드 알고리즘안녕하세요, 이번에는 플로이드 알고리즘을 다루겠습니다. 이제 최단경로 알고리즘인 플로이드, 다익스트라 알고리즘만 다루고 나면 나름 길었던 그래프 파트가 끝납니다. 목차는 눈으로 한 번blog.encrypted.gg 이 문제를 풀며 중요한 부분은, 중간에 거쳐가는 노드를 3중 for문의 가장 바깥에 두어야 한다는 것이다.바킹독님도 강조하시고 있다. 나도 ..
-
BOJ - 2206 벽부수고 이동하기PS 2024. 7. 6. 10:18
https://www.acmicpc.net/problem/2206경로구하기 문제이다.우선 최단경로를 구하는 거기 때문에 bfs를 생각해 볼 수 있다.이제 벽을 뚫는 걸 생각해야 하는데,처음 생각했을때, 벽을 하나씩 부수는 경우의 수를 생각해봤다.그런데, 문제의 조건에서 n 벽을 하나씩 부순다면 1000 * 1000 = 100만 을 기본으로 깔고탐색 1000 * 1000 = 100만. 100만 * 100만 이라는 말도 안되는 시간복잡도가 나오기 때문에 다른 방법을 생각해보기로 했다.두번째로 생각한 방법은 벽을 만날때 이걸 뚫고 가고, 이 뚫는 횟수를 1번까지만 허용하는 거다.그래서 보통 큐에 y좌표, x좌표만 저장하는데 거기다가 추가로 지금까지 벽을 몇개 뚫었나도 저장했다.그리고 1번까지만 벽을 뚫을 수 ..
-
BOJ 2140 지뢰찾기PS 2024. 7. 5. 23:13
https://www.acmicpc.net/problem/2140 우선 생각할 수 있는 건 지뢰의 최대개수를 알아내는 거기 때문에,가생이와 그 맞닿아 있는 부분 빼고 안쪽은 전부 지뢰로 처리하면 되는 걸 생각해낼 수 있었다.그럼 이제 가생이의 숫자들을 보고, 바로 안쪽 부분에 지뢰가 있는지 없는지를 계산해주면 된다. 가생이 바로 안쪽 #이 있는 부분을 돈다.# 주위 8구역을 본다.우선 0이 나온다면, 주위 반경(8구역)에 지뢰가 하나도 있으면 안된다.이 경우, 아무런 처리도 하지 않고 넘어간다. 그리고 주변 구역들이 모두 0이 아니라면, 지뢰를 놓을 수 있다는 뜻이다. 정답을 + 1 해준다.그리고, 지뢰를 놨으므로, 주변 8구역 (물론 지뢰가 있는 부분이 아닌, 숫자가 있는 가생이 부분)에 -1을 다 해..