알고리즘/BFS & DFS (13) 썸네일형 리스트형 [JAVA] 백준 16940번: BFS 스페셜 저지 진행중 import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class baekjoon16940 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); ArrayList[] info = new ArrayList[n + 1]; boolean[] visit = new boolean[n + 1]; int[] order = new int[n + 1]; int[] parent = new int[n.. [JAVA] 백준 16947번: 서울 지하철 2호선 요구사항 역과 순환선 사이의 거리를 공백으로 구분해 출력한다. 문제 해설 최소거리를 확인하는 문제가 아니기 때문에 dfs를 이용하였다. 기존 dfs 문제와 다른점이라고 한다면, 사이클 (순환선) 에 포함되는 역을 찾아야 한다는 것이다. 아래와 같은 로직을 이용하여 문제를 풀어보았다. 1. 지나는 역을 모두 스택에 넣는다. 2. 이미 방문한 역이 면서 거리차이가 2이상일 경우, 해당역은 사이클의 시작지점이자 종결지점이다. 3. 사이클의 시작지점이 나타날 때까지 스택에서 값을 하나씩 빼고, 뺀 값은 사이클의 포함되는 것을 표시해주었다. (isCycle) 4. 마지막으로 사이클의 포함되는 지역은 0을 print 해주고 cycle에 포함되지 않는 값인 경우에는 가장 가까운 cycle과의 거리를 print해주었다.. [JAVA] 백준 16929번: Two Dots 요구사항 게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 확인하라. 문제 해설 최소거리를 확인하는 문제가 아니기 때문에 dfs를 이용하였다. 기존의 dfs 문제와 다른점이 있었다면, 사이클 성립을 확인하기 위해 방문한 곳을 확인하는 로직이 필요하다는 것이었다. 사이클이 성립하려면 최소 4개의 점을 방문하여야 한다는 점을 이용하여 해결하였다. 1. 점을 하나씩 이동할 때마다 dist ary 해당 좌표의 값을 1씩 늘렸다. 2. 해당 점에서 상, 하, 좌, 우의 존재하는 점이 방문한 좌표이고 dist값의 차이가 4 이상이면 cycle이 성립한다고 볼 수 있다. import java.util.Arrays; import java.util.Scanner; public class baekjoon16929 .. [JAVA] 백준 7562번: 나이트의 이동 7576번 토마토 문제와 동일한 유형의 문제다. BFS를 이용하여 문제를 풀었으며 나이트의 위치와 타겟의 위치가 동일한 경우를 제외 한다면, 토마토 문제와 똑같은 방식으로 해결할 수 있는 문제이다. import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class baekjoon7562 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int cycle = sc.nextInt(); int[] aryH = { +2, +2, +1, +1, -1, -1, -2, -2 }; in.. [JAVA] 백준 7576번: 토마토 요구사항 토마토가 모두 익는데 걸리는 최소 날짜를 출력하라 제한사항 익은 토마토에서 상, 하, 좌, 우에 위치한 안 익은 토마토는 다음날 익음 토마토가 모두 익지 못하는 상황이면 -1을 출력 처음부터 모두 익은 상태이면 0을 출력 문제 해설 최소 날짜를 구하는 문제로 BFS를 이용하여야 한다. DFS로 풀 경우에는 최소 날짜를 구할 수 없다. 방문한 경로를 재 방문하는 형태로 문제를 풀 경우에는 DFS가 아닌 브루트포스를 이용한 문제 풀이이다. 브루트포스를 이용할 경우에는 시간 초과 에러가 발생한다. dist[][] = 익는 날짜를 입력 visitInfo[][] = 해당 좌표에 위치한 토마토가 큐에 들어갈 수 있다면 true, 큐에 들어갈 수 없다면 false (중복하여 들어가는 것을 방지) aryH[].. 이전 1 2 다음