https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net BFS 문제다. 전염은 BFS로 풀면 간단할 것 같았는데 우선순위를 어떻게 처리해야 할 지 난감했다. 바이러스 번호, x, y를 하나로 묶어서 정렬을 해야하나 했는데 초마다 정렬해야 할 것 같아서 패스 초만큼 반복을 하고 그 안에서 배열을 계속 반복하며 1일 때만 전염, 그 후 2일 때만 전염으로 하려다가 이것만큼 비효율적인 방법이 없을 것 같아 패스... 총 두 가..
BFS
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net BFS 문제다. BFS에 익숙한 편은 아니라서 정보 없이 문제를 접했다면 BFS를 떠올리지 못했을 것 같다. (BFS 문제임을 알고도 BFS보다 노가다로 구현하려고 했으니까...) 2차원 배열이 아니라는 점도 BFS로 떠올리지 못한 이유 같다. 1차원 배열에서는 앞뒤로 움직이는 두 가지 경우만 고려해주면 된다. 배열에 대한 정보가 입력되는 것이 아니기 때문에 board 배열은 사용하지 않았다. visit 배열..
https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net BFS 문제다. 이어져 있는 1들을 찾기 위해서는 BFS, 연속된 1이 몇 묶음(?) 있는지 알기 위해서는 단순하게 부르트포스를 이용했다. 보통 BFS를 사용할 때는 board 배열, visit 배열 두 개 를 사용한다. 이 문제에서는 입력이 0과 1만 들어오고, 원본을 유지해야 할 필요가 없으므로 visit 배열을 선언하지 않고 board배열의 값을 바꿔주었다. (방문 시 1을 0으로) 1 탐색을 좌..