BaekJoon 18405. 경쟁적 전염(Java)(BFS)(실버1)

문제출처: www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 과정 - disease객체는 필드를 4개 가진다. 바이러스의 종류(virus), 좌표(row, col), 시간초(s). 여기서 s는 bfs를 진행하면서 해당 바이러스가 몇초 지나고 퍼진 바이러스인지 알려줌. - 바이러스가 있는 곳을 미리 찾아놓고 Queue에 저장. - 큐를 virus종류를 기준으로 정렬 - 큐에서 바이러스를 하나씩 꺼내면서 BFS시작. - BFS과..

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-..