Hyun's_Devlog

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

정답 코드

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

구현 문제다. 문제에서 제시한 조건에 맞는 탐색을 통해 구현하면 된다.

풀이

입력이 주어지면 해당 학생의 번호와 좋아하는 사람의 번호들을 n*n개의 배열에 담아 저장한다. 마지막에 행복도 측정을 위해 한번 더 사용해야 하기 때문이다. 매번 정보가 입력될 때마다 교실을 행 - 열 순서로 탐색하면서 아직 배치가 되지 않은 자리에 대해서 인접한 좋아하는 사람의 개수와 인접한 빈 공간의 개수를 반환하는 cntLovers(x:Int, y:Int, lovers:[Int]) 함수를 통해 정보를 반환받은 후 문제에서 제시된 조건에 맞게 입력된 학생의 번호를 담아내야 할 좌표를 갱신한다. 이후 탐색이 끝나면 갱신된 좌표에 학생 번호를 입력한 후 다음 입력을 받는다.

마지막에 행복도 측정을 위해 한번 더 교실을 돌면서 해당 좌석의 번호에 해당하는 cntLovers(x:Int, y:Int, lovers:[Int]) 함수를 통해 행복도를 측정하면 된다.

정답 코드

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

구현 문제다. 톱니의 회전은 간단하게 구현이 가능하지만 문제는 회전하기 전 각 극성을 확인하여 주변 톱니바퀴를 회전해야 할지 회전하지 말아야 할지, 회전한다면 시계방향인지, 반시계 반향인지에 대해 오래 고민했던 문제다.

풀이

처음에는 재귀 호출 방식으로 구현하여 톱니가 회전하게 되면 양 측면의 톱니를 회전할지 말지를 확인 후 재귀 호출하는 방법으로 접근했었다. 하지만 그렇게 접근하게 되면 생각해야 할 조건이 너무 많아지게 된다. 따라서 톱니의 번호와 방향이 입력되면, 4개의 톱니의 회전 방향을 결정하고 난 후 한 번에 처리하는 방법으로 코드를 작성하였다.

톱니의 회전방향을 담아낼 progress: Array(repeating: 0 , count: 4) 배열을 생성한 후 해당 원소가 0이면 회전하지 않고, -1이면 반시계, 1이면 시계방향으로 회전하게 된다. 회전 방향과 톱니의 번호가 입력되면 다음과 같은 동작을 수행한다.

1. 입력된 번호에 해당하는 progress 배열 원소에 입력된 방향 담기
2. 입력된 번호부터 0까지 감소하면서 톱니의 맞닿은 부분의 조건 확인
3. 조건이 맞다면 기존 방향을 뒤집어가며 해당 인덱스의 progess 원소에 방향 담기
4. 입력된 톱니번호부터 마지막 톱니 번호까지 증가하면서 톱니의 맞닿은 부분의 조건 확인
5. 조건이 맞다면 기존방향을 뒤집어가며 해당 인덱스의 progess 원소에 방향 담기

중간에 조건이 맞지 않는다면 반복문은 바로 탈출한다. 이후 마지막에 일괄로 톱니의 회전을 처리하면 된다.

정답 코드

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

구현 문제다. 다리를 어떤 자료구조로 구현해낼지 고민해야 하는 문제다. cpp의 경우 큐 혹은 덱을 이용하여 풀면 되겠지만 스위프트의 경우에 큐나 덱이 없기에 배열을 사용해야 한다.

풀이

다리를 표현하는 bridge: Array(repeating:0, count:w) 배열을 생성하여 허용 중량까지만 담아내고 매 차례마다 원소들을 다음 인덱스로 밀어주는 함수 enter(truck:Int)를 구현하였다. 최대 중량과 현재 중량을 비교하는 부분에서 고민을 했던 문제다. 다리 끝자락에 위치한 트럭이 내리자마자 조건이 맞다면 바로 다음 트럭이 들어가야 하기 때문에 (현재 중량 - 마지막 트럭 무게 + 들어가야 할 트럭 무게) <= 최대 중량이라는 조건으로 매 차례 함수를 수행하였다. 트럭이 들어갈 수 없다면 0 무게를 bridge 배열에 추가하였다.

정답 코드