Lets go show

https://www.codetree.ai/training-field/frequent-problems/problems/tree-kill-all/description?page=1&pageSize=20

우선은 문제를 차근차근 읽어보며 문제를 이해하려고 했다. 문제를 읽다보니 구현해야할 기능이 한 문제 내에 꽤 많아보였고,  평소에 이런 문제처럼 구현해야할 기능들이 많은 경우 조건을 놓치고 디버깅하는데에 시간을 많이 할애해야하는 경우가 많았기에 조금 더 꼼꼼히 읽고 기능을 정리 했다. 

문제의 입력으로 4개의 정수가 들어온다. 처음부터 각각이 의미하는 변수를 다 기억하는 것이 구현해야할 기능을 생각하고 코드를 구현하다보면 헷갈려서 대충 뭐가있다 정도로만 파악해두었다. 

위 그림과 같이 n x n 크기의 보드판에 나무( 0보다 큰 정수) , 벽 (-1 ) , 빈칸 ( 0 ) 에 대한 정보가 입력으로 주어진다. 이후 각각의 나무들은 문제에서 주어진 조건에 따라 성장과 번식을 하게 되고 이후 보드판을 살펴 나무가 있는 곳에 제초제를 뿌리리는데 이 때 제초제를 뿌렸을 때 가장 많은 나무를 박멸할 수 있는 칸을 선택하여 제초제를 뿌려야한다. 이 과정들 (성장, 번식, 제초) 이 1년 주기로 반복된다. 문제는 이 메커니즘으로 작동한다고 보면 되고 추가적으로 고려해야할 상황들이 있다.  

1. 나무의 성장

나무가 있는 칸을 기준으로 상,하,좌,우 방향을 살폈을 때 나무가 존재하는 칸의 수 만큼 해당칸의 나무의 개수가 늘어난다. 즉 위 그림의 46 그루의 나무가 있는 칸을 기준으로 살폈을 때 , 좌,우,하방향에 나무가 존재하고 있으므로 해당칸은 46 + 3 인 49이 된다. 이 때 성장은 성장은 모든 나무에게 동시에 일어난다.

아래의 기능들이 필요하다.

    - 방향을 체크할 때 보드판의 index범위를 벗어 날 수 있으므로 범위를 체크하는 기능 

    - 방향을 살피고 나무를 성장시키는 기능

2. 나무의 번식 

나무가 있는 칸을 기준으로 상,하,좌,우 살폈을 때 빈칸 (벽, 다른 나무, 제초제 모두 없는경우) 이 있는경우 , 각 빈칸에 해당 칸에 있는 나무의수 / 빈칸의 수 만큼의 나무가 번식한다. 이 때 나눌 때 생기는 나머지는 버리고 번식의 과정은 모든 나무에서 동시에 일어난다.

다음과 같은 기능들이 필요하다.

1. 방향을 체크할 때 보드판의 index범위를 벗어 날 수 있으므로 범위를 체크하는 기능 

2. 빈칸의 개수를 체크하고, 번식을 위한 빈칸의 위치를 기억하는 기능 

3. 번식될 나무의 개수를 계산하는 기능

나무의 성장과 번식 과정에서 확인해야 하는 방향이 상,하,좌,우 로 같고 둘다 2중 반복문을 돌아야 하기 때문에 하나의 기능으로 묶어서 구현했다. 

먼저 상,하,좌,우를 나타내는 DIRECTION1 , 대각선 방향을 나타내는 DIRECTION2 ( 이따 제초과정에서 사용됨) 을 정의하고 문제에서 주어진 변수들을 정의해주었다. 

각 변수를 입력받아 문제해결에 필요한 변수들을 초기화 시켜주었다. 

cloneMatrix를 선언해준 이유는 나무가 번식할 때 기존 보드판을 업데이트 하게되면 번식한 칸 마저 기존에 나무가 있던 칸으로 인식되는 일이 발생하기 때문에 정보를 저장해줄 임시 보드판이 필요했다. 

deepCopy 는 2차원 배열 깊은 복사를 위해 따로 만들어주었다. 

이 함수에서 빈칸에 대한 정보를 담고, 나무의 성장이 일어난다. 급하게 코드를 작성한다고 메서드 명이 적절하지 않은 것 같긴하다..

checkMatrixRange 함수는 중복되는 기능이라 따로 분리해주었다. 간단하게 보드판의 indexRange 를 체크해주는 함수이다. 

3. 나무 제초 

각 칸 중 제초제를 뿌렸을 때 나무가 가장 많이 박멸되는 칸에 제초제를 뿌린다. 나무가 없는 칸에 제초제를 뿌리면 박멸되는 나무가 전혀 없는 상태로 끝이 나지만, 나무가 있는 칸에 제초제를 뿌리게 되면 4개의 대각선 방향으로 k칸만큼 전파되게 된다. 단 전파되는 도중 벽이 있거나 나무가 아얘 없는 칸이 있는 경우, 그 칸 까지는 제초제가 뿌려지며 그 이후의 칸으로는 제초제가 전파되지 않는다. 제초제가 뿌려진 칸에는 c년만큼 제초제가 남아있다가 c+1년째가 될 때 사라지게 된다. 제초제가 뿌려진 곳에 다시 제초제가 뿌려지는 경우에는 새로 뿌려진 해로부터 다시 c년동안 제초제가 유지된다.

만약 박멸시키는 나무의 수가 동일한 칸이 있는 경우에는 행이 작은 순서대로, 만약 행이 같은 경우에는 열이 작은 칸에 제초제를 뿌리게 된다.

편의를 위해 제초제년 수에 따라 -2 부터 작아지는 방향으로 생각하고 구현했다.

다음과 같은 기능이 필요하다.

1. 가장 많이 제초되는 칸을 구하는 기능 

2. 전파 될 곳을 확인하고 제초제를 전파하는 기능 

3. 전파된 땅의 값을 제초제 년수에 따라 업데이트하는 기능 

4. 제초된 나무들의 합을 구하는 기능 

5. 제초되는 최대 나무가 같은칸이 존재하는 경우 주어진 조건에 따라 인덱스를 계산하는 기능

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

처음에 문제를 천천히 읽어 보면서 이 문제의 특징을 먼저 파악해 보려고 했다.
1. 연산자의 우선순위가 없다.
2. 중첩 괄호를 사용할 수 없다.

위 두가지 특징을 염두해두고 문제 케이스에 대해 살펴 보기로 했다.

예제 입력 1에 있는 예시를 가지고 먼저 가능한 케이스에 대해 고려 해보면

• (3+8)*7-9*2
• (3+8)*(7-9)*2
• (3+8)*7-(9*2)
• 3+(8*7)-9*2
• 3+(8*7)-(9*2)
• 등등...

위 케이스들을 고려하면서 괄호를 추가하는 것에 대한 규칙성이 있는지에 대해 고민을 해보았지만 규칙이 보이지 않았다. 문제에서 주어진 N의 최대 길이가 19이고 시간 제한이 0.5초이기 때문에 따로 규칙을 고려하지 않고, 가능한 모든 경우의 수를 다 찾더라도 시간내에 풀 수 있을 것이라고 생각했다. 

먼저 주어진 입력을 받기 위한 버퍼를 정의했다. 이 후 연산자와 숫자를 따로 처리하는 것이 편할 것 같아서 각각을 받는 ArrayList 를 정의했다. 입력값에는 (zerobased index 기준) 0을 포함한 짝수번째 값에는 숫자, 홀수번째 값에는 연산자가 들어오는 규칙이 있기 때문에 이를 활용해서 입력값을 저장해 주었다. 

이제 정답값을 구하기 위한 솔루션만 구현하면 되고 이는 완전탐색을 위해 dfs를 활용하여 구현하기로 했다. 이 때 괄호를 사용하지 않는 경우의 값 또한 구해주어야 한다는 점을 고려해야 한다. 연산자 인덱스를 기준으로 계산을 생각해서 구현했다. 

사실 처음에는 괄호를 어떻게 처리해야 할 지 감이 잘 오지 않았다. 그 이유는 수식 앞에서 부터 순서대로 괄호를 넣는 케이스를 예시로 생각했었고 아래와 같이 앞에서 부터 케이스별로 괄호를 넣을 수 있는 방법을 구현하려고 하니 복잡하고 잘 떠오르지 않아서 많이 헤맸다. 

e.g.) 
1. 3+8*7-9*2 (= (3+8)*7-9*2))
2. 3+(8*7)-9*2
3. 3+(8*7)-(9*2)

...

하루정도 리프레쉬를 하고.. 다시 생각해보니 백트래킹으로 풀면 되는데.. 라는 생각이 들어서 아래와 같이 구현했다. 연산자 인덱스를 기준으로 조건문을 생각했고, 모든 경우의 수를 다 계산할 수 있는 방법이다. 

연산에 대한 함수는 따로 분리해주었다. 위 switch-case 문은 자바 11 에서는 지원하지 않는 문법(자바 11이후 부터 지원하는 문법)이라 백준에 제출할 때는 기존 switch-case expression을 사용해서 제출했다. 물론 if문을 사용해도 무방하다. 

아직까지 백트래킹에 대한 아이디어가 바로바로 떠오르지 않는 것을 보니 더 연습이 필요하다고 느꼈다.