알고리즘 (123) 썸네일형 리스트형 [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 ··· 13 14 15 16 다음