Hyun's_Devlog

https://www.acmicpc.net/problem/16236

그래프 탐색 문제다. 너비 우선 탐색으로 풀었다. 상어의 움직임에 대해 오래 고민했던 문제다.

풀이

상, 좌, 우, 하 순서로 너비 우선 탐색을 수행한다. 빈 곳이거나 같은 사이즈의 물고기를 만난다면 큐에 담아 이동을 수행, 자신보다 작은 사이즈의 물고기를 만나면 해당 좌표를 다른 배열에 저장하였다.

탐색이 끝난 뒤 문제의 조건에 맞게 먹을 수 있는 물고기가 담긴 배열을 시간, x좌표, y좌표 순으로 정렬한 뒤 가장 가까운 좌표로 이동하여 해당 물고기를 먹으면 된다. 처음에는 이러한 정렬 없이 먹을 수 있는 물고기를 만나면 바로 먹어버리고 탐색을 종료했는데, 같은 거리에 있는 먹을 수 있는 물고기에 대한 조건이 안 맞아 오답이 나왔다.

탐색 함수는 상어가 이동한 좌표와 걸린 시간을 반환하게 하였다. 상어의 좌표에 이동이 없는 경우 먹을 수 있는 물고기가 없는 것으로 판단하여 반목문을 빠져나오는 것으로 코드를 작성했다.

정답 코드

https://www.acmicpc.net/problem/9019

그래프 탐색 문제다. 너비 우선 탐색으로 해결했다.

풀이

0부터 9999에 해당하는 움직임을 담는 문자열 배열을 생성한 뒤, 입력되는 A부터 시작하여 너비 우선 탐색을 수행한다. D, S, L, R 연산에 해당하는 숫자를 만들고 해당 인덱스의 배열에 현재까지의 움직임에 해당 움직임 문자열을 더하여 탐색을 수행한 뒤 탐색이 끝나면 B인덱스의 배열 값을 출력하면 된다.

정답 코드

시간초과를 마주하여 조금 더 동작을 빠르게 해결하기 위해 27번 라인에 B번째 배열의 값이 갱신되면 탐색을 곧바로 종료하는 조건을 추가하였다.

https://www.acmicpc.net/problem/9663

백트래킹 대표 유형 문제다. 예전에 시도했던 문제지만 시간제한에 걸려 풀지 못했던 문제다. 결국 다른 분의 풀이를 확인하고 풀 수 있었다.

풀이

해당 문제는 같은 행과 열, 그리고 우측에서 좌측으로 내려오는 대각선과 좌측에서 우측으로 내려오는 대각선이 겹치는지 확인하여 N번의 조건을 백트래킹을 통해 풀어야 한다. 단순하게 매 횟수마다 2차원 배열의 true false를 통해 조건을 탐색하게 된다면 시간 초과가 일어나게 된다.

이번 풀이는 열, 좌측 하행 대각선, 우측 하행 대각선을 담당하는 Bool 타입 1차원 배열을 각각 따로 생성하여 조건을 확인하는 방법이다. 행에 대한 배열이 없는 이유는 한 행에 하나의 퀸만 놓을 수 있기에 따로 퀸을 놓게 되면 바로 다음 행으로 넘어가기 때문이다.

N = 4일 경우의 각 배열의 양상이다. 2차원 보드판 위치의 기준으로 각 배열에 확인해야 하는 인덱스를 넣어 놓았다. 3가지 배열 모두 해당 인덱스에 퀸이 없을 경우에만 퀸을 배치하고 다음 열로 넘어가게 된다.

정답 코드

https://www.acmicpc.net/problem/16234

그래프 탐색을 통해 해결할 수 있는 문제다. 너비 우선 탐색으로 진행했다.

풀이

지도를 탐색하면서 인접 배열과의 인구수를 비교, 조건에 맞다면 큐에 담아낸 뒤 마지막에 큐에 담겨있는 좌표를 확인하면서 값을 갱신한다. 문제에서는 몇 차례의 변동이 일어났는지 횟수를 요구하기 때문에 반복문으로 수행한 뒤 Bool 타입의 flag 변수를 사용하여 종료 여부를 확인하였다.

정답 코드

https://www.acmicpc.net/problem/15685

구현 문제다. 규칙에 대한 파악과 x축과 y축 반전, 격자 칸의 수 등 실수를 유발하기 위한 장치들이 많은 문제라고 생각한다. 드래곤 커브에 대해 파악하는 데에 시간이 오래 걸렸던 문제다. 이런 유형의 경우 시간 내로 풀이를 생각하는 게 중요하다고 생각된다.

풀이

드래곤 커브의 움직임에 대해 이해가 필요한데, 문제에 주어진 번호에 따른 방향을 보면 힌트를 얻을 수 있다. 다음 세대의 움직임은 이전 세대의 다음 인덱스의 방향으로 움직이게 된다. 단 이전 세대의 움직임의 역순으로 추가를 시켜야 한다. 정리된 표를 통해 보면 이해하기 쉽다.

일반적인 2차원 배열을 통해 풀어내려면 x축과 y축을 반대로 생각하고 풀어야 한다. 이어서 해당 문제는 격자가 100칸 즉 배열로 생성하려면 가로세로 101칸의 배열을 생성해야 100칸의 격자가 만들어진다. 본인의 경우 생각 없이 가로 세로 100칸의 배열을 생성했다가 오답 판정을 받았다. 입력되는 드래곤 커브는 격자의 범위를 벗어나지 않는다는 조건이 있으니 범위 체크는 하지 않아도 된다. 드래곤 커브로 둘러싸인 격자를 세는 방법은 인접한 4칸을 확인하며 세면 된다.

정답 코드

https://www.acmicpc.net/problem/14500

완전 탐색 문제다. 다른 풀이가 있을까 생각해보았지만 결국 해당 패턴에 대한 회전과 대칭을 고려해 모든 범위에 대해 비교를 해야 한다.

풀이

해당 패턴을 담은 배열을 생성하여 입력받은 지도의 모든 좌표를 돌면서 최댓값을 갱신하면 된다. 패턴은 좌측 상단을 기점으로 x축과 y축의 범위를 지정하였다. 패턴을 생성할수있다면 최대값을 갱신, 패턴이 범위 밖의 좌표라면 갱신하지 않는다.

정답 코드

처음에 대칭에 대한 조건을 확인하지 않아 오답 판정을 받았다. 해답을 생각해내는 시간보다 패턴을 배열로 옮기는 데에 더 많은 시간이 들었던 문제였다.

https://www.acmicpc.net/problem/21610

구현 문제다. 문제를 잘못 이해하여 많은 시간을 허비했던 문제. 항상 느끼지만 집중해서 글을 읽는 점이 부족한 것 같다.

실수했던 부분은 구름이 생성될 때 해당 바구니의 물은 2씩 사라지지만, 해당 구름이 비를 내릴 때에는 1씩 내린다는 점이다.

풀이

입력범위가 크진 않지만 시간제한이 1초로 제한되어있고 구름이 이동하면서 비를 내리는 게 아니라 이동한 후에 비를 내리기에 구름의 이동을 한 번에 계산하여 처리하도록 접근했다. 구름 배열 cloud: [(Int, Int)] 를 생성하여 구름을 담아내고, 구름이 소멸할 때 구름이 있던 자리를 확인하는 visited: [[Bool]] 배열을 사용하여 물 복사 부분을 처리하였다.

정답 코드

https://www.acmicpc.net/problem/14499

구현 문제다. 주사위의 회전 방향을 생각하면서 문제를 풀면 간단하게 풀 수 있다.

풀이

주사위를 6칸짜리 배열로 할당하여 순서대로 주사위의 윗면, 북, 동, 서, 남, 바닥면으로 할당한 뒤 입력되는 방향에 맞게 주사위 원소들을 이동하였다. 즉 주사위 면은 가만히 있고, 주사위에 적힌 숫자가 회전하는 개념으로 문제를 풀었다. 

정답 코드