반응형 알고리즘 PS/Flood Fill5 [백준] 2468번 - 안전영역 (Java)(○) https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1. 빗물높이는 주어지지 않으니 1~100까지 증가시키면서 섬의 개수를 탐색해서 가장 큰 수를 도출하자. 2. 상/하/좌/우로 탐색하면서 DFS 함수 내부에서 빗물높이와 비교해서 낮으면 스킵하는 식으로 구현하자. 3. 아무지역도 물에 잠기지 않을 수도 있다가 뜻하는 케이스는? 1. 빗물높이를 1부터 시작해서 TC 중 실패하는게 있었다. 2. 아무지역도 물에 잠기지 않을수도 있다는 노트가 빗물높이를 0으로.. 2022. 9. 1. [백준] 10026번 - 적록색약 (Java)(○) https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. R / G / B를 별도의 그룹으로 구분해서 탐색한 결과와 R과 G를 동일 그룹으로 묶어서 탐색한 결과를 도출하는 문제이다. 1. 상하좌우 탐색을 하는 DFS 알고리즘 문제이다. 2. DFS 함수를 2가지 종류로 만들어서 R/G/B를 모두 구분하는 함수와 R-G / B 로 구분하는 함수로 만들어서 순차적으로 호출한다. 더보기 import java.util.*; /* [백준] 10026.. 2022. 9. 1. [백준] 4963번 - 섬의 개수 (Java)(◎) https://www.acmicpc.net/problem/4963 1. 상하좌우대각선까지 탐색해야 한다. 2. w와 h가 0 0이면 테스트케이스를 종료한다. 1. map에서 상하좌우대각선을 탐색한 후 1이면 방문처리한다. 2. 메인함수에서 for문을 돌려서 1을 발견하면 dfs를 돌리고 섬개수를 ++한다. 1. 입력함수를 TC를 while문으로 받고 w와 h가 0이면 break 하는 식으로 구현 2. 확장할 때 새 지점이 섬인지 바다인지 체크하는 구문 빼먹음. if (A[nx][ny] == 0) 더보기 import java.util.*; /* [백준] 4963번 - 섬의 개수 (Java) */ public class Main { static int w, h; static int A[][]; static .. 2022. 8. 31. [백준] 1012번 - 유기농 배추 (Java)(◎) https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1. 지렁이는 상/하/좌/우로만 연결된 배추로만 이동할 수 있으니, 상하좌우로 연결된 배추군집의 수를 구하면 된다. 2. 입력형식이 배추의 좌표이므로 이를 받아서 인접배열로 구성한다. 1. 상하좌우로 확장하면서 배추그룹을 만들면서 이동하면 된다. 2. dfs의 파라미터는 x, y 좌표를 넘겨준다. 3. 메인함수의 for문에서 1을 반견해서 dfs를 호출하면 새로운 그룹의 시작이므로 그때 count++를 해준다.. 2022. 8. 31. [백준] 2667번 - 단지번호붙이기 (Java)(◎) https://www.acmicpc.net/problem/2667 1. 정점은 집이다. 상하좌우로 탐색해서 1이면 다시 탐색을 계속한다. 2. 총 단지 수와 각 단지마다 집의 개수를 출력한다. 1. 메인함수에서 for문으로 dfs 함수를 호출한다. 2. 방문처리 된 곳이면 스킵하다가 새로운 1을 만나면 새로운 단지의 시작이다. 3. 방문배열을 방문처리할 때 count++를 하다가 새로운 단지를 만나면 초기화하자. 4. 단지 내 집의 수를 오름차순으로 정렬해서 출력해야 한다. 1. 입력함수에서 in.nextInt()로 받으면 안되고 한줄 단위로 문자열로 받은 다음 toCharArray()로 문자배열로 변환한 후에 ch - '0'을 해서 정수형으로 변환시켜서 배열에 저장해야 한다. 2. 출력함수에서 집의 수.. 2022. 8. 31. 이전 1 다음 반응형
