https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 구현 문제다. 해당 문제는 시간제한이 짧다. 시간제한을 신경써서 최대한 간단하게 작성하려기보단 구현을 먼저하고 시간제한을 신경쓰려고 했다. 한 칸에 여러 나무가 존재할 수 있다는 점이 생각보다 까다로웠다. 나무의 위치를 입력받는 배열로 [100][3]으로 2차원 배열 / [10][10][102]로 3차원 배열 두 가지를 생각했다. 2차원 배열은 각각의 값을 저장하는 것이고, 3차원..
Algorithm
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net BFS 문제다. 문제를 해결하기 위해 돌아온 길이 많아서 시행착오는 후에 작성하겠다. 문제 해결은 일반 BFS에 8방향 검사를 추가로 시행했다. 방문 배열을 3차원으로 설정해 8방향 이동 능력을 몇 번 사용했는지 체크했다. 간단한데도 이 방법을 생각해내는데 오래 걸렸다... 그리고 이 문제에서 오류가 발생하기 쉬운 점은 입력이 세로 가로가 아닌 가로 세로인 점이다. 세로를 먼저 입..
https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net BFS 문제다. 처음 떠올린 방법은 덩어리를 찾아 덩어리 별로 같은 숫자로 저장하는 것이다. 그 후 각 덩어리의 테두리로부터 본인 숫자보다 큰 덩어리에 닿는 경우의 수를 모두 찾은 후 최솟값을 출력하는 것이다. 시간이 오래 걸릴 것 같아 최대한 반복을 덜 돌리려고 고민을 했다. 모든 경우의 수를 찾지 않고, 다리의 최소 길이보다 이동 수가 많아지면 함수를 바로 종료하는 것이다. 그리고 테두리를 따로 구..
https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net BFS 문제다. 문제 이해에 이틀을 쓴 것 같다...ㅋ 불도 사람처럼 1분에 한 칸만 움직이는 줄 알았는데 불은 1분에 4방향으로 다 퍼지는 것이었다. 이 부분을 해결하고 나니 첫 번째 의문은 해결됐고 다른 의문이 생겼다. 몇 분이 걸리는지가 중요한 문제이기 때문에 한 타임에 딱 한 번만 움직여야 하는데 그 부분 구현이 의문이었다. 나는 큐의 사이즈를 구한 후 그만큼만 돌리면 된다고..
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 덱을 이용한 구현문제다. 스택을 사용해도 될 것 같다고 생각을 했는데 맨 처음 넣은 원소를 확인하기 힘들고 언제 양방향에 넣고 뺄지 모르니까 덱을 사용했다. 헷갈리는 부분이 존재했는데 뱀의 머리를 구하려면 front, 꼬리를 구하려면 back이라고 생각했다. 큐에는 꼬리가 먼저 들어가고 머리가 나중에 추가되는 방식이라 머리가 back, 꼬리가 front였다. 뱀의 머리에 대한 위치를 찾고, 방향에 맞추어..
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net BFS와 구현이 함께 있는 문제다. 문제의 알고리즘 분류를 보니 DFS로도 풀 수 있는 것 같다. 그림 문제처럼 덩어리를 파악하고 치즈 문제처럼 배열 전체에 BFS를 적용하는 횟수를 구해야 한다고 생각했다. 경험이 있는 문제들의 응용 문제 같아서 알고리즘이 쉽게 떠올랐다. 이 문제의 주의점은 올해(?) 녹은 빙산이 0이 되어 다른 빙산에 영향을 주면 안된다는 것이다. 이걸 해결하기 위해서는 ..
