본문 바로가기

Algorithm/Graph Search Algorithm30

BOJ G3 2206 벽 부수고 이동하기 JAVA 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 읽기 해당 문제는 최단 경로를 구하는 문제라 판단하고 그리 어렵지 않을 것이라 생각했다. 하지만 20퍼센트 쯤에서 본 “틀렸습니다”라는 문구..!! 일단 문제 풀이를 시작해보자. 문제 풀기 NxM 크기의 일반적인 맵에 0으로 표현된 빈 칸, 1로 표현된 벽이 존재한다. 0, 0에서 N-1, M-1까지 가는 최단 거리를 찾으면서, 그 중에서 벽 한 개는 뚫을 수 있다. 이는 크게 어렵지 않게 생각했다. 최단 거리이기 때문에 DFS와 .. 2024. 4. 9.
BOJ G4 9019 DSLR JAVA 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 읽기 일단 해당 문제를 읽고 나서는 완전 탐색 말고는 딱히 방법이 떠오르지는 않았다. 그래서 DFS와 BFS를 생각했고, DFS는 깊이 우선 탐색이라 끝이 없을 것 같아서.. 백퍼 시간 초과 날 거 같았다. 그래서 최소 연산의 개수를 구하는 것이기 때문에 BFS를 바로 적용해서 해결했다. 문제 풀기 문제는 크게 어렵지 않다. 주어진 명령어마다 요구사항에 따라서 정확하게 구현한다면 틀리지는 않을 것이다. 또한 같은 숫자로 또 탐색하지 않도록 하기.. 2024. 3. 27.
BOJ G4 13913 숨바꼭질4 JAVA 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 읽기 해당 문제는 가장 빨리 갈 수 있는 시간, 그리고 그 때의 루트를 출력해야 한다. 이전에 가장 빨리 갈 수 있는 시간을 문제는 풀어봤던 기억이 있다. 하지만 이 문제는 루트까지 출력해야 한다! 즉, BFS + 루트 출력 문제라 볼 수 있다. 문제 풀기 BFS를 쓰는 이유는, 당연하겠지만 최소 시간을 구하기 때문이다. 이 문제는 완전 탐색을 해야 하는데, DFS, BFS 중에서 고르라면 최소 시간만 얻으면 되기 때문에 주.. 2024. 3. 22.
BOJ S2 2805 나무 자르기 JAVA 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 읽기 이 문제는 일단 입력 값이 너무 컸기 때문에 바로 이분 탐색을 써야 겠다고 생각이 들었다. 입력 값을 한번 보자. 나무의 수 N : 1~1,000,000(백만) 필요한 나무 길이 M : 1 ~ 2,000,000,000(이십억) 나무의 높이 : 0~1,000,000,000(십억) 만약 완전 나이브하게 풀이한다면, 나무를 자를 높이를 0에서부터 십억까지 1씩 증가시키면서, N개의 나무를 다 잘라보고, 총합이 필요한 .. 2024. 3. 20.

티스토리툴바