반응형 floodfill9 [백준] 1926번 - 그림 (Java) https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net map : 1과 0으로 구성. 그림 : 상하좌우가 1로 연결된 것 그림의 갯수와 가장 큰 그림의 넓이를 출력한다. 그림이 하나도 없는 경우에는 가장 큰 그림의 넓이는 0을 출력한다. 입력정보 세로축 N : 2022. 10. 10. [백준] 3055번 - 탈출 (Java) https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 지도는 R행 C열로 이루어짐. 비어있는 곳 '.' 물이 차있는 곳 '*' 돌은 'X' 비버의 굴은 'D' 고슴도치의 위치는 'S' 고슴도치는 매분마다 인접한 상/하/좌/우의 칸 하나로 이동할 수 있다. 물도 매분마다 인접한 비어있는 칸으로 확장한다. (이것도 상/하/좌/우?) 물과 고슴도치는 돌을 통과할 수 없다. 고슴도치는 물로 차있는 지역으로 이동할 수 없다. 물도 비버의 굴로 이동할 수 없다. 고슴도치는.. 2022. 10. 5. [백준] 2146번 - 다리 만들기 (Java) https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net N x N인 맵에서 여러 개의 섬이 있다. 각 섬을 연결하는 다리를 한 개만 건설한다고 할 때 가장 짧은 거리를 구하라. BFS탐색으로 각 섬은 탐색할 수 있다. 그런데 각 섬과 다른 섬과 가장 최소거리는 어떻게 구하지? 시간 제한 : 2초 메모리 제한 : 192MB 지도크기 : N 2022. 10. 2. 플러드 필(Flood Fill) 알고리즘 플러드 필은 다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 그림판에서 색 채우기 명령으로 동일한 색을 전부 바꿔버리는 것과 동일하다. 플러드 필 문제는 BFS/DFS 알고리즘으로 풀 수 있다. [BFS의 풀이과정] 1. 시작하는 칸을 큐에 넣고 방문 표시를 한다. 2. 큐에서 원소를 꺼내어 그 칸에 상/하/좌/우로 인접한 4개의 칸에 대해 탐색을 한다. 3. 해당 칸을 이전에 방문했다면 무시하고, 처음 방문했다면 방문 표시를 하고 해당 칸을 큐에 넣는다. 4. 큐의 모든 원소가 빌 때까지 2를 반복한다. 5. 모든 칸이 큐에 1번씩만 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. ※ 참고 : https://blog.encrypted.gg/941 2022. 10. 1. [백준] 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 다음 반응형
