BFS

📖 문제 https://www.acmicpc.net/problem/1600   💡  풀이 방식• BFS필요 자료구조- 상하좌우 이동을 위한 4방향 배열 dx,dy- 말인 경우 대각선 8방향 이동을 위한 배열 hx, hy- 격자판 정보 저장할 2차원 int형 배열- 해당 좌표에서 방문 여부와 말 이동찬스 사용 횟수를 저장하는 3차원 boolean형 배열 ⇒ chk[세로][가로][말 이동찬스 사용 횟수]  1. 정수 K를 입력받는다.2. 가로 W와 세로 H를 입력받는다.3. 크기가 H*W 인 격자판의 정보를 입력받는다.4. 맨 왼쪽 위부터 맨 오른쪽 아래까지 최단 거리로 간다고 했으므로 맨 왼쪽 위에 있는 (0, 0)부터 BFS를 수행한다.  - 2차원 배열의 좌표 내 방문 여부 뿐만 아니라, 매 탐색마..

📖 문제  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   💡  풀이 방식• BFS필요 자료구조- 시추관 위치(열) 별 석유량 저장용 배열- BFS에서 석유 덩어리의 열 위치 저장용 Set (중복 제거 위해)  격자를 돌면서 방문하지 않은 1인 칸의 위치에서 BFS를 수행한다.  - 석유 덩어리의 열 위치 저장용 Set을 활용한다.  - 방문하지 않은 1인 칸을 방문하며, 해당 열의 위치를 Set에 저장하고, 석유 덩어리 개수를 구한다.  - Set에 저장된 열 위치들에 현재 위치에서 구한 석유량을 누적해 더한다.   💥 유의사항land 배열을 그대로..

📖 문제 https://www.acmicpc.net/problem/9205   💡  풀이 방식• 플로이드 와샬필요 자료구조- 위치들 저장용 리스트- 위치들 중 두 지점 간 방문 가능한지 표시하는 2차원형 boolean형 배열 1. 모든 위치들을 입력받아 리스트에 저장한다.2. 모든 위치들 중 2개를 골라 두 위치 간의 맨해튼 거리를 계산한다. (맨해튼 거리가 1000 이하라면 해당 거리로 이동할 수 있다.)3. 지점 A에서 B로 이동 가능하고, B에서 C로 이동 가능하다면 A에서 C로 이동 가능하므로 이동 가능하다는 표시를 한다. (플로이드-와샬)  💥 유의사항플로이드-와샬은 시간 복잡도가 O(N^3)이므로 사용 시 주의가 필요하다.  🔺 코드123456789101112131415161718192..

📖 문제 https://www.acmicpc.net/problem/1240   💡  풀이 방식• BFS 1.  인접 리스트를 만들고 N-1개의 연결 정보를 양방향으로 저장한다.2. M개의 노드 쌍에 대해 첫 번째 노드부터 두 번째 노드까지의 거리를 구한다. (BFS)   🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576import java.util.*;import java.io.*; public class Main {    static int N,M;    static ListNode>[..

📖 문제 https://www.acmicpc.net/problem/15723   💡  풀이 방식• 플로이드-워셜 i는 k고, k는 j면, i는 j다. - N개의 전제를 입력받으며 a는 b라고 처리한다. → connected[a][b] = true- 플로이드-워셜로 i는 k고, k는 j면, i는 j 가 되도록 처리한다.- M개의 결론이 맞는지 확인하며 a는 b라면(= connected[a][b] == true) T를, 아니라면 F를 출력한다.   🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748import java.util.*;import java.io.*; public class Mai..

📖 문제  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr    💡  풀이 방식• BFS + DP4가지 방향에서 오는 방향 별 최소 비용을 저장하기 위해 방향까지 합친 3차원 배열을 사용하는 것이 포인트!이 때, 단순 bfs로만 탐색하면 각 방향마다 달라지는 최소 비용을 지나칠 수 있으므로 dp (메모이제이션)을 사용한다. - 4방향 탐색을 할 때, 처음 실행하거나 방향이 바뀌지 않은 경우에는 현재 비용에서 +100원만큼, 방향이 바뀐 경우에는 +600원만큼 이동하도록 한다. (방향 전환하느라 +500, 직진하느라 +100 한 번 더 하므로)int next..

📖 문제 https://www.acmicpc.net/problem/17142   💡  풀이 방식• 조합 + BFS[필요 자료구조]- 바이러스 객체 ⇒ (행,열, 거리 값) 저장- 인접한 4방향 탐색할 dx/dy 배열- 바이러스 위치 저장용 객체 리스트- 초기 빈 칸 개수 저장하는 int형 변수 zeroCnt  연구소의 상태를 입력받는다.빈 칸(0)인 경우, zeroCnt에 +1 한다.바이러스(2)인 경우, 해당 위치와 0을 리스트에 저장한다.빈 칸의 갯수가 0이라면, 0을 출력하고 종료한다. / 그게 아니라면, 바이러스 위치 중 M개를 뽑아 바이러스를 심고 퍼뜨리는 데 걸리는 최소 시간을 계산한다.M개 바이러스 뽑기 > 조합 (백트래킹)바이러스 퍼뜨리기 > BFS- M개 바이러스를 뽑았으면, 해당 위..

📖 문제 https://www.acmicpc.net/problem/16956  💡  풀이 방식• BFS 늑대 주변만 울타리로 감싸면 된다. 1. 늑대의 위치를 큐에 저장한다.2. 각 늑대의 위치들을 돌며 인접한 칸을 방문하며 이동할 다음 칸이 ① 빈 칸(.)인 경우에는 울타리를 설치하고, ② 양(S)이라면 함수를 종료한다.3. 만약 늑대가 양이 있는 칸으로 이동할 수 있다면 0을 출력하고 종료한다. / 이동할 수 없다면 1을 출력하고, 격자를 출력하낟.   🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970im..

📖 문제 https://www.acmicpc.net/problem/16509  💡  풀이 방식• BFS 필요 자료구조- 상하좌우 이동용 dx/dy배열- 대각선 이동용 cx/cy 배열- 탐색 위한 BFS용 큐- 좌표 방문 표시용 2차원 boolean형 배열  상 위치에서부터 BFS를 시작해 왕에게 도달하는 횟수를 구한다.- 만약 현재 큐에서 뽑은 위치값이 왕의 위치와 같다면, 여태 구한 이동 횟수를 출력한다.- 그렇지 않다면, 경로가 막혔는지 판단하며 탐색을 진행한다.   ㄴ 먼저 상하좌우 방향으로 한 칸 이동한다.   ㄴ 마저 이동 가능한 경우, 상하좌우 움직임에 따라 방향을 2개씩 매칭한 후 해당 방향으로 확산시키며 이동 횟수를 갱신한다.// 경로가 막혀있는지 판단용 함수private static ..