공부하는 블로그

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 익은 토마토와 인접한 토마토는 하루의 시간이 지나면 익게 된다. 박스에 토마토가 전부 익는데 걸리는 시간을 구하는 문제이다. import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; class Main { static int N; static int M; static int[][] tomatos; static int[] dx = {-1, 0, 1, 0}; sta..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net N x M 행렬로 주어진 미로를 탐색하는 문제이다. (1, 1)에서 출발하여 (N, M)까지 도달하는데 필요한 최소 칸 수를 찾아내야 한다. import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; class Main { static int[][] maze; // 미로 static boolean visit[][]; // 방문 여부 체크 static int[] dx = {-1, 0, 1, 0}; // 시계방향으로..

DFS와 BFS는 그래프를 탐색하는 방법이다. 둘의 차이를 간단히 말하자면 깊이(자식)를 우선으로 탐색하냐, 너비(형제)를 우선으로 탐색하냐 이다. DFS (Depth First Search) 깊이 우선 탐색(DFS)은 루트(root) 노드 또는 임의의 노드를 기준으로 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 즉, 한 곳을 선택하여 우선적으로 끝까지 탐색한 후에야 다른 인접한 노드를 방문할 수 있다. 이 방법은 그래프의 모든 노드를 방문하고자 할 경우 유용하다. 코드로 구현할 때에는 스택(stack)과 재귀함수를 사용한다. 재귀함수를 이용하여 DFS를 구현하는 과정은 다음과 같다. * 재귀함수 : 자기 자신을 호출하는 함수 0. 시작 노드가 없을 경우에는..