[백준] dfs - 2583번 영역 구하기 (Java)
문제링크 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 접근한 방법 연결 요소의 개수를 구하는 문제이므로 dfs 풀이방법 1인 값이 상, 좌, 하, 우로 연결되어 있는 범위를 묶어 그 안의 있는 요소의 수를 세면된다. 1. 특정한 지점의 주변 상, 좌, 하, 우를 살펴본 뒤에 주변 지점 중에서 값이 1이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다. 2. 방문한 지점 에서 다시 상, 좌, 하, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다. 방문..
2021. 5. 23.
[백준] dfs - 2667번 단지번호붙이기 (Java)
문제링크 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 접근한 방법 연결되어있는 노드의 개수를 구하는 문제이므로 dfs 풀이방법 1인 값이 상, 좌, 하, 우로 연결되어 있는 범위를 묶어 그 안의 있는 요소의 수를 세면된다. 1. 특정한 지점의 주변 상, 좌, 하, 우를 살펴본 뒤에 주변 지점 중에서 값이 1이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다. 2. 방문한 지점 에서 다시 상, 좌, 하, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다. 방문시마다 요소의 ..
2021. 5. 22.
[백준] dfs - 1743번 음식물 피하기 (Java)
문제링크 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진 www.acmicpc.net 접근한 방법 연결된 노드의 묶음이 포인트인 문제이므로, dfs 풀이방법 1인 값이 상, 좌, 하, 우로 연결되어 있는 범위를 묶어 그 안의 있는 요소의 수를 세면된다. 1. 특정한 지점의 주변 상, 좌, 하, 우를 살펴본 뒤에 주변 지점 중에서 값이 1이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다. 2. 방문한 지점 에서 다시 상, 좌, 하, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든..
2021. 5. 21.
[백준] dfs - 1012번 유기농 배추 (Java)
문제링크 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 접근한 방법 dfs 풀이방법 이 문제는 DFS로 해결할 수 있다. 0인 값이 상, 하, 좌, 우로 연결되어 있는 노드를 묶어 묶음의 수를 세면된다. 1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 1이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다. 2. 방문한 지점 에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다. 3. 1~2번의 과정을 모든 노드에 반복하며 방문하..
2021. 5. 16.
