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 배열..
Algorithm
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 탐색을 좌..
https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 구현 문제다. 블록이 높이 쌓인 곳을 찾는 게 우선이라고 생각했다. 1. 처음 생각한 방법은 첫 줄을 기준으로 잡고 기준 보다 더 큰 지점을 찾아가는 것이었다. 큰 지점을 찾기까지 기준의 높이와 해당 줄의 높이 차를 합산하는 방법을 생각했다. 그러나 끝 줄이 항상 높지 않고 그러면 전 기준까지의 합산을 되돌려야 하기 때문에 비효율적이라 생각했다. 이 방법을 패스하고 다른 방법을 ..
