백준

[백준] 1697 숨바꼭질 (JAVA)

✉️문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 📝 접근 최단거리를 구하는 문제이다. DFS로 풀 수 있을 것 같지만, DFS로 구현하면 커팅 기법을 사용해도 지수 시간 복잡도를 가지기 때문에 시간 내에 통과하기 어렵다. 따라서 BFS를 이용해야 한다. 🗝 문제풀이 package baekjoon; import java.util.LinkedList; import java.util.Queue; import jav..

[백준] 7569 토마토 (JAVA)

✉️문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 📝 접근 7576번과 똑같은 BFS 문제이다. 여기서 배열이 2차원 -> 3차원으로 변경된 문제라고 생각하면 된다. https://brightmango.tistory.com/323 [백준] 7576 토마토 (JAVA) ✉️문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주..

[백준] 7576 토마토 (JAVA)

✉️문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 📝 접근 Queue를 이용한 BFS를 이용한다. 🗝 문제풀이 1. 입력을 받을 때 input == 1이면 큐에 집어넣는다. // 입력을 받을 때 input == 1이면 큐에 집어넣는다. for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int input = sc.nextInt(); box[i][j] = input; if..

[백준] 2606 바이러스(JAVA)

✉️문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 📝 접근 이 문제를 풀기 위해서는 2가지를 알아야 한다. DFS 또는 BFS -> 본인은 DFS를 통해 문제를 풀었다. -> DFS의 핵심은 재귀이며, 똑같은 정점을 방문하지 않도록 추가적인 체크배열이 필요하다. public static void DFS(int idx) { ch[idx] = 1; for(int n : graph.get(idx)) { if(ch[n] == 0) { answer++..

[백준] 10830 행렬 제곱 (JAVA)

✉️문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 📝 접근 1. B의 범위를 보면 int형 범위가 넘어간다. 따라서 long으로 선언해야 한다. 2. 행렬 배열은 int형으로 선언해도 된다. (제곱하고 각 원소를 1000으로 나누기 때문) 3. 제곱을 100,000,000,000번 하면 시간제한인 1초 안에 풀 수 없다. 따라서 분할 정복법을 이용한다. 🗝 문제풀이 package baekjoon; import java.util.Scanner; publ..