BFS 썸네일형 리스트형 [프로그래머스] PCCP 기출문제 2번 (석유 시추) / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 PCCP의 기출문제로 석유시추라는 이름을 가진 문제입니다. 제한 사항에 정확성과 효율성을 확인하는 부분이 있어 조건에 맞도록 구현 뿐 아니라 가능한 효율적이도록 코드를 짜야합니다. 시추관은 특정 열을 모두 관통하는데 해당 열에 포함된 석유 덩어리를 모두 시추가 가능합니다. 하나의 시추관을 사용할 때 시추가능한 최대 석유의 양을 구하는 문제입니다. 문제를 해결하기 위해선 각 열별로 시추.. 더보기 [백준] 9205 맥주 마시면서 걸어가기 / 자바(Java) 문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 해설 기초적인 BFS문제입니다. 편의점의 좌표만이 나와있기 때문에 어느 편의점을 방문했는가 여부를 알기위해 입력값을 받을 때 편의점별로 추가로 인덱스를 저장하여 줍니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedLis.. 더보기 [백준] 1600 말이 되고픈 원숭이 / 자바(Java) 문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 해설 원숭이가 2차원 판을 시작지점에서 도착지점까지 이동하는 최소 횟수를 구하는 문제입니다. 최소횟수를 얻으며 각 계산이 독립적이므로 완전탐색이 필요하므로 해결방법으로 BFS가 떠오릅니다. 여기서 K번만 가능한 체스의 나이트처럼 뛰는 횟수가 문제가 됩니다. 특정 위치의 방문 여부가 K가 남아있는가에 따라 다음 이동 가능 여부가 달라지기 때문에 이를 해결하기 위해서 dp배열을 .. 더보기 [백준] 4485 녹색 옷 입은 애가 젤다지? / 자바(Java) 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 해설 입구에서 출구까지의 모든 경로의 가장 낮은 숫자의 합을 구하는 문제입니다. 각 위치별 경로의 최소합을 얻기위해 dp 지도를 만듭니다. dp[i][j] 는 (i,j)위치까지 가는 경로의 최소합을 의미합니다. BFS를 통해 4방탐색으로 다음 위치는 이전 위치 + 진입 숫자보다 작은 경우 갱신하며 새로 큐에 넣는 방식을 통해 dp에 항상 최소값을 갱신할 수 있도록 구현했습니.. 더보기 [백준] 2589 보물섬 / 자바(Java) 문제 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 해설 BFS를 사용하면 될 듯한 문제입니다. 단 문제의 조건에서 최단거리 중 가장 먼 곳의 거리를 구해야합니다. 다행히 각 섬별로가 아닌 단 한 가지 경우만 찾으면 되므로 2차원 배열에 지도 정보를 넣고 각 땅 별로 BFS를 통해 갈 수 있는 최대 거리를 구해 각각을 비교하는 방식으로 해결할 수 있는 BFS의 기본을 익힐 수 있는 문제였습니다. 코드 import java.io.BufferedRe.. 더보기 [프로그래머스] 리코쳇 로봇 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 2차원배열에서의 4방탐색과 bfs를 통해 목표까지의 최단 횟수를 구하는 문제입니다. bfs를 구현하기 위해 큐를 사용합니다. 큐에는 특정 좌표(r,c)를 담는 1차원 배열을 넣어줍니다. 여기서 중요한점! 여러번 이동하다 이전에 갔던 곳을 표시하는 boolean 2차원 배열이 필요합니다. 목표까지의 최단 횟수를 구하기 때문에 이전에 갔던 곳을 간다면 목표로 도달하는데 그 곳보다 무조건 .. 더보기 [프로그래머스] 무인도 여행 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 상하좌우로 연결된 같을 모두 더하고 떨어져있는 요소들을 오름차순으로 정렬하면되는 간단한 4방탐색와 완전탐색을 섞은 문제입니다. 3가지 코드들을 이용해 문제를 해결할 수 있습니다. 입력을 다루기 쉽게 2차원 배열로 생성(map) 4방탐색을 시작할 위치를 반복을 통해 선정 4방탐색과 BFS 리스트를 배열로 변환, 정렬 1번. 입력을 다루기 쉽게 2차원 배열로 생성 문제에서 주어진 maps.. 더보기 이전 1 다음
