농부공학자

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS로 풀었다. 중요한 점은... 1에서 0으로 옮겨가서 숫자를 바꾸는 식으로 짰는데 1이 여러개 있을 수 있으므로 BFS() 함수를 돌릴 때 x,y 좌표를 Queue에 넣으면 계산이 한번에 되어버린다. 뭔말이냐면 이렇게 (0, 0)에서 0(안익은) 을 쭉 훑어서 4까지 가버린다. 그래서 이미 map[][] 배열을 쭉 훑어서 1인 x,y 좌표를 queue에 넣어놓고 함수를 실행시..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net BFS 연습하려고 들어갔다. 정답률이 50프로가 넘길래 만만하게 보고 들어갔는데 1도 모르겠어서~ 다른분꺼 참고함 (https://yongku.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-14502%EB%B2%88-%EC%97%B0%EA%B5%AC%EC%86%8C-%EC%9E%90%EB%B..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net DFS로 풀었음 탐색 문제는 다 비슷비슷 한 것 같다. 보자마자 DFS 아니면 BFS를 써야겠다 싶은.... 쉬운 문제만 푸는건가? 뭐 암튼.. 여기서 주의할점은.... 문제에 그려진 배열로 생각하면 안된다는거랑... 입력에 주어지는 숫자대로 배열을 만들면 안된다는...것이다. 우선 문제에 그림이 이렇게 그려져있는데 우리는 배열을 만들 때 (0,0)이 왼쪽 위에 가게 하므로 이..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 참고 : https://settembre.tistory.com/377 ㅡㅡㅡㅡㅡㅡㅡㅡㅡ C ㅣ ㅣ ㅣ ㅣ ㅣ R 이런 느낌인건 탐색 써서 상하좌우 살펴봐야 한다는건 알겠는데 이 문제에서는 겹치지 않고 최대 움직일 수 있는걸 구하는 거여서 이 부분을 생각하는게 어려웠다. 그래서 다른분꺼 참고함 나는 상, 하, 우, 좌 순서로 보기 때문에 첫번째로 여기 4개를 살펴보고 더 이상 나아갈 수 없게..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net DFS를 이용해서 풀었다. 위 문제에서 주의할 점은 매번 풀던 문제들은 배열이 0, 1 두 가지로 이루어져 1의 뭉탱이 개수를 구하거나... 하는 것이었는데 얘는 R, G, B 3가지의 뭉탱이 개수를 구하는 것이다... 그래서 dfs() 함수에 tmp 변수를 넣어 주변 값이 tmp와 같은 값일 때 재귀를 수행하는 방식으로 짜야했다. 코드 import java.io.BufferedReader..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 위 문제도 DFS로 풀어보았다. 음... 안전 영역을 찾기 위해 0~ 지역의 높이가 가장 높은 곳까지 대입하며 안전 지역이 가장 많은 곳을 찾았다. 코드(수정함) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public cl..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net DFS 알고리즘을 이용하여 풀었다. 전형적인 DFS 문제로 이해할 수 있는데 무한 루프로 돌리다가 w h 값이 0 0 이 되었을 때 멈춰야한다는 것이 추가되었다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net DFS 알고리즘을 이용해 풀었다. 위의 문제는 연결 요소의 개수를 묻는 문제로 연결이 되어있는 요소의 개수를 출력하면 된다.. 첫 번째 예시를 그려서 살펴보면 위와 같이 나온다. 음....그래서 2중 ArrayList에 각 요소가 연결되어 있는 값을 넣고 visited[] 라는 배열을 만들어 방문했는지 확인하고 재귀하는 방식을 사용할 ..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS를 공부할 때 살펴본 문제와 같은 문제였다. (https://www.youtube.com/watch?v=7C9RgOcvkvo) 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.S..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 얘도 그냥 전형적인 DFS/BFS 문제이다. DFS 연습중이라 DFS로 풀음 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Baek1012 { // DFS public static int count[] ..