728x90 반응형 코딩테스트/백준104 [백준/java] 17086번: 아기 상어2 - BFS https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 푸는데 한세월 걸린 문제.. 각 영역으로부터 상어까지의 최대 거리를 BFS로 탐색한 결과를 받는다. package bfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.. 2021. 8. 26. [백준/java] 13335번: 트럭 (프로그래머스와 동일) https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 트럭의 갯수, 다리의 길이, 다리의 최대 하중이 주어지는 문제. 두개의 큐를 이용하여 해결하였다. 다리를 건너기위해 대기하는 큐, 다리 위를 지나가는 트럭 큐. while문을 돌때, 두 큐 중에 한 큐라도 비어있지 않은지를 조사해야 다음의 경우들을 모두 조사할 수 있다. (1) 다리에 차가 없을 때 (2) 다리에 차가 있으나 한대 더 들어가서 하중을.. 2021. 8. 25. [백준/java] 1520번: 내리막길 - DFS + DP https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 이번 문제는 얼핏보면 단순히 DFS 문제처럼 보인다 하지만 제출하고 보면 마주하게 되는 시간초과 행렬을 보면.. 뭐지? DFS 만으로 풀리는 문제가 아닌가 싶은 생각이 든다. 시간 초과가 나는걸 보고 이건 단순한 DFS 문제가 아님을 알아야했다. DFS에 DP를 더한 문제였다. DP의 방법은 두가지 방법이 있다. Top Down과 Bottom up 방식이 있는데 그 두가지 방법은 밑의 링크에서 설명되어.. 2021. 8. 19. [백준/java] 1987번 : 알파벳 - DFS https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제풀이 처음으로 DFS를 사용해서 풀어봤다. 골드 4 난이도 치고는 문제 자체는 어렵지 않다 나왔던 알파벳이 또 나오면 더 이상 진행하지만 않으면 되는데, 나는 HashSet을 이용하여 중복으로 나온건지 체크하였다. package dfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStrea.. 2021. 8. 19. [백준/java] 2589번: 보물섬 - BFS, 브루트포스 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 브루트 포스와 BFS 탐색이 결합된 문제이다. 처음에 어떻게 보물의 위치를 구해야하나 싶었지만 같이 풀은 친구의 힌트로 두 점의 위치를 구할 필요가 없다.(브루트 포스라서!) 이중 for문으로 무차별 대입을 해줘서 step이 가장 큰, 즉 두 점 사이의 거리가 가장 큰 값을 반환하면 된다. 두 점 사이의 거리가 가장 먼 곳이 보물의 위치이기 때문에, 그냥 거리값만 반환하면 된다. package bfs.. 2021. 8. 18. [백준/java] 2206번: 벽 부수고 이동하기 - BFS https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 지금까지 내가 풀어본 BFS 문제 중에 가장 어려웠던 문제였다. 그냥 기존에 풀던 방법대로 풀다가는 풀리지 않는다. 특히나, 기존에 입력한 int형 2차원 배열 값을 변경해서는 결코 안된다. 지문을 읽다보면 벽이 있을 때, 벽을 한번은 부술 수 있는 기회가 주어진다. 그렇다고 해서 map[ny][nx] = 0; 으로 값을 바꿔버리면 제출했을 때 오답이 된다. 정답을 찾기위.. 2021. 8. 17. 이전 1 2 3 4 5 6 ··· 18 다음 728x90 반응형
