BaekJoon 7576. 토마토(Java)(BFS)(실버1)

문제출저 : www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 풀이 과정 - pair객체는 필드를 3개 가진다. 좌표(row, col)와 date. 여기서 date는 bfs를 하면서 +1씩되는 날짜를 의미 - 익은 토마토를 미리 찾아놓고 Queue에 저장. - 저장한 토마토를 하나씩 꺼내면서 BFS시작. - BFS과정을 거치면 날짜가 1씩 커지면서 모든 토마토를 익게하고, 다익었다는 가정하에 가장 큰 maxDate가 정답. 소스코드 packa..

BaekJoon 1937. 욕심쟁이 판다(Java)(DFS,DP)(골드3)

문제출저 : www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 문제 조건 - N*N 크기의 대나무 숲이 주어져 있을 때, 지금있는 지점의 대나무 보다 많은 대나무 쪽으로 상하좌우 4개의 방향 중 한곳으로 이동할 수 있다. - 4개의 방향 모두 대나무가 현위치의 대나무 개수보다 적을 경우 판다는 스트레스받아 죽는다. -판다가 최대한 살 수 있는 일수(K)를 출력. 풀이 과정 - 어느 한 지점의 노드를 들어 감 - 그 노드 값 기준 상하좌우 중 자기 자신..

BaekJoon 9466. 텀 프로젝트 (Java)(DFS)(골드4)

문제출저 : https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 www.acmicpc.net 문제 조건 - 텀프로젝트를 해야 한다. 학생은 자신을 포함한 단 한명을 선택해서 팀을 꾸릴 수 있다. - 자세한 설명은 문제 참조. - 그래프가 cycle을 이뤄야 팀 생성 가능. 답은 팀에 속하지 못한 학생들의 수 이기 때문에 N - (cycle을 이룬 학생 수) 가 됨. 풀이 과정 cycle을 찾아서 그에 해당하는 학생수를 찾으면 된다고 생각. 코드 구현 (1) 첫번째 시도 packag..

BaekJoon 1074. Z (Java)(분할 정복)(실버1)

문제출저 : https://www.acmicpc.net/problem/1074 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 �� www.acmicpc.net 문제 조건 - 2^n * 2^n 크기의 배열에서 z모양의 규칙으로 방문해서 번호를 매겼을 때 - 임의의 (r,c)의 점이 몇번째 번호인지를 출력하는 문제 풀이 과정 첫 번째 시도 : z규칙을 이해하고 2^n * 2^n의 2차원 배열을 만들어서 번호를 부여한 다음, 번호 출력 두 번째 시도 : 2^n * 2^n의 배열을 만들지 않고, 분할과 정복을 이용하여 번호를 찾는 알..

BaekJoon 17472. 다리 만들기 2 (Java)(BFS, DFS, UNION-FIND)(골드3)

문제출저 : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 조건 - 그래프 문제(MST 최소신장트리 문제) - 문제에 대한 자세한 설명은 위에 출처 참조 풀이 과정 1. x축(col)과 y축(row)의 좌표 값을 나타내는 객체 pair가 필요하다고 생각, 나중엔 다리객체도 필요 했음 2. 붙어있는 섬끼리 하나의 묶음으로 만들어야 되는데, 그것을 labeling 이라고 했음 (1) BFS로 labeling (2) DF..

BaekJoon 1012. 유기농 배추(Java)

문제출저 : https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 문제 조건 - 그래프 문제(연결 그래프의 개수를 찾는 문제) - 가로길이 M(1 ≤ M ≤ 50), 세로길이 N(1 ≤ N ≤ 50) - 배추 위치 K(1 ≤ K ≤ 2500) 풀이 생각 1. DFS 2. BFS -> Union-Find는 필자의 기술 부족일 수도 있지만, 위치 좌표 x,y가 주어지고 그 좌표들의 상하 좌우를 계속 체크해야 하는 문제 이기 때문에 간선위주의 풀이법인 Union-..

BaekJoon 11724. 연결 요소의 개수(Java)

문제출처: 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 문제 조건 - 방향 없는 그래프가 주어 졌을 때, 연결 요소의 개수를 구함 - 정점 개수 : 1 ≤ N ≤ 1,000, 간선 개수 : 0 ≤ M ≤ N×(N-1)/2 풀이 생각 1. DFS 2. BFS 3. Union Find 코드 구현 (1) DFS package 백준; import java.io.BufferedRead..

BaekJoon 2565. 전깃줄(Java)

2565. 전깃줄 문제출처: https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 조건 - 두 전봇대 A와 B, 각각의 전봇대에는 다른 전 봇대로 전깃줄이 뻗어 갈 수 있는 번호가 있다. - 전봇대 위에서부터 차례대로 번호가 매겨짐 - 전깃줄 개수(N) = 1; j--) { if (location[j] != 0 && location[j] > value) cnt++; } if (cnt >= 1) { answer2++; } System.out.printl..