BFS

[JAVA] 코드트리 : 2개의 사탕

문제 코드트리 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제가 보이지 않으면 https://www.codetree.ai/frequent-problems 여기서 찾아볼 수 있다. 이번 문제는 따로 코드를 모듈화 하지 않고 일자로 나열해서 작성해서 가독성이 매우 좋지 않지만 코드 트리에서 자바 풀이를 따로 제공하지 않아 도움이 될까 하여 업로드한다. 해결방법 옛날에 필통으로 하던 구슬 미로 찾기 게임이 생각나는 문제였다. 구슬 대신 사탕을 기울여서 EXIT라고 적힌 밖으로 빨간색 사탕만 빼내야하는데 밖으로 빼내기 위한 최소 횟수를 찾는 문제이다. 전형적인 시뮬레이션 문제라고 할 수 있는데 시뮬레이..

[JAVA] Programmers : 등산코스 정하기

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오랜만에 글을 작성한다. 그 동안 꾸준히 알고리즘은 학습하고 있었지만 글 작성을 할 여유가 없어서 작성하지 못했는데 이 문제는 해결 방법을 공유해두면 좋을 것 같아서 작성해보려고 한다. 문제읽기 XX산은 n개의 지점으로 이루어져있는데 각 지점은 1 ~ n 까지 번호가 붙어있고 해당 지점들은 출입구, 쉼터, 산봉우리 중 하나이다. 각 지점으로 이동할 때 등산로를 이용해야하는데 이 때 등산로별로 소요되는 시간이 다르다. 이 때 각 지점에 방문할 때마다 휴식을 취할 수 있는데 휴식 없이 이동해야하는 시간 중 ..

[JAVA] 백준 17141 : 연구소 2

문제 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 해결방법 오랜만에 BFS 탐색 문제이다. 이 문제의 경우 연구소에 특정 위치에 바이러스를 놓아서 연구소 전체를 바이러스에 감염시키려는 승원이의 계획을 도와주는 문제이다. 문제에서 맵에 2로 표시된 구역이 바이러스를 놓을 수 있는 공간인데, 그 공간 중 M만큼 바이러스를 놓았을 때 연구소 전체를 감염시킬 수 있는 가장 빠른 시간을 구해야 한다. 즉, 모든 경우의 수를 탐색해야 하는 완전 탐색 문제라고도 할 수 있다. 조합을 찾을 때는 비트 마스킹을 사용해서 방문 처리를..

[JAVA] 백준 1963 : 소수 경로

문제 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 해결방법 문제를 읽어보면 가능한 비밀번호는 1000 ~ 9999 사이의 숫자이다. 그렇기 때문에 에라토스테네스의 채를 이용해서 9999까지의 소수를 찾아내고 현재 비밀번호에서 각 자리수를 하나씩 변경하며 그 수가 소수라면 다음으로 또 한자리는 변경하는 방식으로 목표 비밀번호까지 최소한의 횟수를 찾는 문제이다. 순서를 정리하면 1. 9999까지 소수를 찾는다. 2. 각 자리수를 변경하며 목표 비밀번호를 찾는데, 거쳐가는 비밀번호도 모두 소수인지 확인해야한다. 추가적으..

[JAVA] 백준 1194 : 달이 차오른다, 가자.

문제 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 해결방법 방문 체크가 중요한 문제이다. 열쇠가 a ~ f 가 존재하고 각 열쇠에 해당되는 문이 A ~ F가 존재한다. 방문 체크를 열쇠를 아예 들고 있지 않을 때, a만 들고 있을 때, a와 b를 들고 있을 때 등으로 나누어서 체크를 해주어야 한다. 그렇게 하면 총 6개 열쇠를 모두 방문 체크를 해주어야 되기 때문에 좌표값 + 6 해서 8차원 배열을 사용해야 한다. 그래서 비트 마스크를 사용한다. 비트마스크를 사용하면 아예 사..