![]()
📖 문제 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..
![]()
📖 문제 https://www.acmicpc.net/problem/1504 💡 풀이 방식• 다익스트라필요 자료구조- 인접 배열 리스트- 시작점에서 각 정점까지 가는 최단 거리 저장용 int형 배열- N개의 각 정점에 대한 boolean형 방문 표시 배열- (목적지, 거리) 정보를 저장하는 객체 1. E개의 입력을 받으며 두 정점 간 거리 정보를 양방향으로 저장한다.2. 꼭 지나쳐야 하는 두 정점 v1, v2를 입력받는다.3. ① 경로 1 > v1 > v2 > N을 지날 때의 최단 거리와, ② 경로 1 > v2 > v1 > N을 지날 때의 최단거리를 계산한다. (다익스트라)4. 두 최단 거리가 모두 최댓값인 INF보다 크거나 같으면, 경로가 없는 것이므로 -1을 출력하고, 그게 아니라면 경로 1..
![]()
📖 문제 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/9944 💡 풀이 방식• 백트래킹1. 값을 입력받으면서 격자 안의 값이 장애물(*)인 경우, 방문 처리하고 방문한 칸의 갯수(cnt)를 1 증가시킨다.2. 한 칸만 빈 칸인 경우, 해당 케이스의 이동 경로 수는 0이다.if(cnt == N*M) answer = 0; // 한 칸만 빈 칸인 경우 3. 모든 칸을 탐색하며 방문한 적 없는 점에서,4방향 탐색을 통해 1) 격자 범위 내에 있고, 2) 방문하지 않은 칸을이동 처리했다가 안 했다가 하며 이동 경로 수를 구한다. (백트래킹)for(int i = 0 ; i [백트래킹 함수]- 인자 : x좌표, y좌표, 이동 횟수(result), 방향 번호(dir), 방문 갯수(cnt)s..
![]()
📖 문제 https://www.acmicpc.net/problem/16938 💡 풀이 방식• 백트래킹+ 브루트포스1. 문제들을 배열에 입력받고, 이 배열을 난이도 기준 오름차순 정렬한다.2. 2~N개까지 캠프에 사용할 문제들을 고른다. (백트래킹)for(int i = 2 ; i [백트래킹 함수] - (종료 조건) 목표 갯수만큼 뽑았다면, 문제에서 제시한 2가지 조건을 만족하는지 확인하고 방법 수를 갱신한다.(여기서 리스트를 오름차순 정렬하지 않는 이유는, 이미 배열을 입력받고 오름차순 정렬해두어서 리스트에 저장할 때 이미 오름차순으로 난이도를 저장해 두기 때문이다.)if(cnt == target) { int sum = 0; List list = new ArrayList(); ..
![]()
📖 문제 https://www.acmicpc.net/problem/3019 💡 풀이 방식• 구현, 브루트포스 1. 블록 모양에 따라 올라와야 하는 바닥면의 높이를 저장한다.2. 바닥면에 대해 블록을 끝까지 내릴 수 있는지 반복문으로 검사한다. ⇒ 각 번호에 맞는 빈 공간 수를 뺐을 때 모두 같은 값이 나오면 놓을 수 있는 자리이다!! (참고) 🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152import java.util.*;import java.io.*; public class Main { static int C,P; static int[] map; ..
![]()
📖 문제 https://www.acmicpc.net/problem/16509 💡 풀이 방식• BFS 필요 자료구조- 상하좌우 이동용 dx/dy배열- 대각선 이동용 cx/cy 배열- 탐색 위한 BFS용 큐- 좌표 방문 표시용 2차원 boolean형 배열 상 위치에서부터 BFS를 시작해 왕에게 도달하는 횟수를 구한다.- 만약 현재 큐에서 뽑은 위치값이 왕의 위치와 같다면, 여태 구한 이동 횟수를 출력한다.- 그렇지 않다면, 경로가 막혔는지 판단하며 탐색을 진행한다. ㄴ 먼저 상하좌우 방향으로 한 칸 이동한다. ㄴ 마저 이동 가능한 경우, 상하좌우 움직임에 따라 방향을 2개씩 매칭한 후 해당 방향으로 확산시키며 이동 횟수를 갱신한다.// 경로가 막혀있는지 판단용 함수private static ..
![]()
📖 문제 https://www.acmicpc.net/problem/15683 💡 풀이 방식• 시뮬레이션 + 백트래킹 + 브루트포스 각 CCTV의 타입을 받아, 각 타입에 맞춰 회전된 상태를 조합해 사각지대의 최소값을 구한다.CCTV 타입이 1( → )인 경우 : 북(0 / ↑), 남(1 / ↓), 서(2 / ←), 동(3 / →)CCTV 타입이 2( ↔ )인 경우 : 서동(23 / ↔), 북남(01 / ↕ )CCTV 타입이 3(↑→)인 경우 : 북동(03 / ↑→) , 남동(13 / ↓→) , 남서(12 / ↓←) , 북서(02 / ←↑)CCTV 타입이 4( ←↑→ )인 경우 : 북서동(023), 북남동(013), 남서동(123), 북남서 (012)CCTV 타입이 5(↕↔)인 경우 : 북남서동(..
