KOMAS

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

• 문제 이해
• 해결 방법
• 구현 코드

문제 이해

이전에 풀었던 별 찍기 - 10번 문제와 비슷한 형태였다.

3 * 2^N을 (3, 6, 12, 24, 48...)인 수를 입력받아서 삼각 형안에 삼각형 형태로 별을 재귀적으로 찍으면 된다.

문제의 예제로 봤을 때 입력된 수는 높이가 되고, 너비는 높이 * 2인 것을 알아챌 수 있었다.

그리고 대략적으로 윗 삼각형은 현재 높이의 2로 나누어지는 부분이고, 아랫 삼각형 두개는 현재 너비를 2로 나누어

두 부분으로 나누어져 재귀적으로 그려지는 것을 대략적으로 파악한 후 문제 해결 방법을 생각하였다.

해결 방법

처음 생각은 정가운데에 어떻게 index를 찾아서 별을 찍을까 고민하다가 가장 작은 삼각형의 형태인

높이가 3일때에 높이와 너비 index에 빼는 방식으로 별을 찍으면 찍을 수 있을 것 같았고 그 방법으로

별을 찍어 문제를 해결했다. 그러므로 재귀 함수의 종료 조건은 높이가 3이므로 size가 3일 때 종료되게끔 하였다.

이러한 문제 유형은 2차원 배열을 입력의 크기만큼 생성해두고 index 조정만 잘해준다면 문제없이 풀 수 있는 문제이다.

가장 오른쪽 끝, 맨 밑의 index를 알아내어 그 부분부터 index를 빼서 별을 찍을 생각이었으므로

끝 값 index에 현재 해당되는 size만큼 빼주면 쉽게 재귀적으로 높이와 너비 부분을 인자로 넣어 재귀 함수를 호출할 수 있다.

가장 먼저 재귀 함수내에서 현재 size를 2로 나누어 간격으로 활용하였다.

예를 들어 24가 입력으로 들어오면 간격은 12가 되어 현재 간격으로 높이와 너비를 적절히 빼주면 된다.

가장 윗 삼각형은 높이가 반으로 줄어드므로 현재 높이(24) - 간격(12)으로 처리해주었다.

너비는 총 48이고 4분의3 지점이 오른쪽 끝이 되므로 현재 너비(48) - 간격(12)으로 처리했다.

아래 두개의 삼각형은 높이는 가장 아래를 사용할 것이기 때문에 그대로 사용하고,

너비는 현재 너비(48) - 간격 * 2(24)로 첫 번째 아래 삼각형을 재귀 호출하고,

두 번째 아래 삼각형은 높이와 너비를 그대로 사용하면 되었다.

종료 조건에서 별을 찍을 때는 높이와 너비가 가장 아래, 가장 오른쪽이 들어왔으므로 적절히 빼주어 삼각형을 그려주게끔 하였다.

index는 크기를 기준으로 사용했으므로 -1을 추가로 더해주면 알맞게 찍힌다.

출력을 할 때 System.out.println()을 쓰면 시간초과가 걸려서 BufferedWriter를 사용했다.

구현 코드

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

• 문제 이해
• 해결 방법
• 구현 코드

문제 이해

기본적으로 BFS를 이용한 위, 아래, 좌, 우를 0이면 1로 바꾸는 Flood fill 문제인 것은 알 수 있었다.

이 문제는 BFS의 기본 문제들과는 다르게 Flood fill의 시작 위치가 여러 개인 점이 기본 문제와는 달랐다.

Queue의 특성상 시작 토마토의 위치들인 1인 지점들을 bfs 함수를 실행 하기 이전에 전부 미리 넣어준 후

bfs를 하면 될 것 같다는 점은 쉽게 파악할 수 있었다.

그 이후 bfs를 이용해 기존하던 방식으로 각 상자에서 토마토가 1이므로 1의 주변을 익어가게끔 하면 되는 문제였다.

-1인 벽을 처리해주어야 하는 요구사항이 있지만 어차피 bfs를 할 때 0인 조건만 1로 만들어주면 되므로 0일 때만

새로운 토마토 객체를 생성해주면 되었다.

해결 방법

bfs를 실행하기 이전에 시작 토마토들인 1의 위치를 전부 Queue에 넣어 주어주어야 했다.

넣어주는 과정은 입력을 받는 과정에서 1이라면 Queue에 행, 열 위치를 알 수 있는 토마토 객체를 생성하여 넣어주었다.

추가로 토마토 객체를 생성할 때 인스턴스 변수로 며칠이 지났는지 확인할 수 있는 day를 만들어 주었다.

새로운 객체를 생성할 때 현재 Queue에서 꺼낸 반복문을 돌아가는 객체의 day 인스턴스 변수에 +1 만 해서 새로 객체를 생성할 때 지정해준다면

새로운 토마토가 생성될 때마다 이전 토마토의 day에 +1을 하므로 최소일 수를 알 수 있다.

최소일수를 알고자 할 때 모든 객체의 day의 max를 계산하면 시간이 추가로 걸리므로 이 방법보다는 전역 변수에 day를 선언해두고

가장 마지막에 생성되는 객체의 day를 전역변수 day에 저장한다면 그것이 마지막 익는 토마토의 날짜가 될 것이다. 

bfs는 2차원 배열을 탐색할 때 자주 처리해주는 2차원 배열의 범위를 벋어 나지 않게 설정해주고, 0이면 토마토 객체를 생성하고

그 부분을 1로 바꿔주어 다시 Queue에 생성되지 않도록 하였다. 0 일 때만 처리하므로 -1 인 벽을 신경 써주지 않아도 된다.

구현 코드

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

• 문제 이해
• 해결 방법
• 코드 구현

문제 이해

금방 해결할 수 있을 줄 알았는데 생각보다 시간이 걸린 문제다.

일단 문제 자체에서 재귀적인 패턴으로 해결하라고 명시되어있다.

아마 명시되어있지 않더라도 문제를 읽어보면서 3^n이 입력으로 들어오는 조건이 있을 때 입력/3으로 나누어지니 재귀를 파악할 순 있다.

예를 들어 입력이 27이라면 별이 그려지는 부분이 27 -> 9 -> 3 -> 1으로 3으로 나누어져 그려지므로

재귀적인 방법을 사용해야 한다는 걸 금방 알아챌 수 있을 것이다.

해결 방법

일단 3^N인 수를 입력받으면 행 3개, 열 3개 총 9개 부분으로 나눈 후 재귀적으로 해결해야 한다.

그러므로 재귀 함수의 선언부를 (행의 마지막 위치, 열의 마지막 위치, 3으로 나눌 size)로 만들었다.

행, 열을 마지막 위치가 아닌 시작 위치로 해도 무관하다.

중요한 점은 3으로 나눈 size만큼 더해주거나 빼주면서 아홉 부분을 재귀 함수를 호출한다는 것이다.

9                            
3,        6,        9
1, 2, 3  4, 5, 6  7, 8, 9

여기서부터 size/3을 간격이라고 하겠다.

입력이 9라고 예를 들면 3^n을 입력으로 받으므로 9에서 간격인 3씩 빼는 방식을 선택했다. 이 숫자를 행, 열 따로 재귀적으로 넘겨주면 된다.

직접 구현해보진 않았지만 3, 6, 9로 넘겨주지 않고 시작 위치부터 간격을 더하면서 1, 4, 7을 함수의 인자로 넘겨줘도 해결될 것 같다.

구현하면 반복이 될 때마다 행과 열을 간격만큼 빼주면서 총 9 부분을 호출하도록 이중 반복문을 사용했다.

그리고 정 가운데 부분은 별을 그리지 않을 것이므로 정 가운데 부분에 해당되는 부분은 재귀 함수를 호출하지 않도록 했다.

재귀 함수의 종료 조건은 size가 1이 되면 재귀 함수를 종료하게 끔 하였다.

행, 열의 크기가 1이므로 이 부분에서 전역 변수로 선언된 2차원 배열[입력 크기][입력 크기]에 별을 그려주면 된다.

급하게 생각하지 말고 2차원 배열의 index를 유지시키면서 해당 행과 열 지점을 재귀 함수로 넘겨 호출을 해주고

재귀 함수의 종료 조건만 잘 지정해준다면 풀렸던 문제였다.

결국 중요한건, for문을 이용한 index 증감 조절을 잘해주면 된다. 

이 외에도 재귀 함수를 이용한 비슷한 문제들이 백준에 있는데

재귀 함수 호출 시에 넘겨줄 index만 잘 생각해서 범위 조정해준다면 전부 해결할 수 있다.

코드 구현

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

• 문제 이해
• 해결 방법
• 구현

문제 이해

먼저 N, M 두 숫자를 입력받는다. N은 1부터 N까지를 의미한다.

M은 출력 자릿수를 결정한다.

이 문제 N과 M (1)은 M 자릿수를 출력하며 1부터 N까지 중복 없이 출력하는 경우이다. 이 문제의 출력은 결국 순열을 의미한다.

N과 M 문제 시리즈 같은 경우는 순열, 중복순열, 조합, 중복 조합 등을 백트래킹을 이용해서 구현하는 방법을 훈련할 수 있다.

이 문제는 백트래킹을 몰랐다면 풀기 어려웠을 것 같다.

해결 방법

우선 재귀 함수를 이용하여 자리수를 하나씩 채워간다. 즉 재귀가 될 때마다 자릿수가 다음 자릿수로 넘어간다.

재귀의 인자로 자리수 번호를 0부터 시작하여 앞부터 채워나간다.

재귀가 진행될 때 마다 0 1 2 3 4 자릿수를 채워나간다. 자릿수를 넘치면 종료 조건이 된다. 

재귀 함수 내에서 반복문으로 1부터 N까지 진행하게 해 두고 반복 문안에 재귀 함수를 만들어두면 1 -> 1- > 1 ->....로 재귀 함수가 호출이 되고, 자릿수가 넘쳐서 종료 조건을 만나면 이전 재귀함수로 돌아와 1 -> 1 -> 1 -> 2 이런 식으로 다음 반복을 진행하게 되어 모든 경우의 수를 출력할 수 있을 것이다.

하지만 이 방법은 중복순열이 되므로 중복된 숫자를 출력하지 않게 하도록 방문처리를 해주어야 했다.

중복된 숫자를 출력하지 않도록 하는 중복처리는 boolean[] 배열을 이용해서 재귀 함수 호출 이전에 for문 안에서

방문하지 않았다면 방문 처리한 후 다음 재귀 함수를 호출해서 다음 재귀로 넘어가도록 하였다.

이렇게 되면 다음 재귀 함수에서 1부터 사용하려 하겠지만 방문처리가 되었다면 다음 숫자의 반복으로 진행이 되므로

중복된 숫자가 출력되지 않도록 처리를 해줄 수 있다.

재귀 함수가 종료조건을 만나면 이전 재귀 함수 위치로 돌아오고 해당 수의 방문처리를 해제해준다.

여기서 이런식으로 방문 처리를 해제해주면 어차피 다음 반복문은 +1 이므로 해당 자릿수에서는 같은 숫자를 출력하지 않을 것이다.

* 예를들어 1234 출력 후 1234가 다시 안 되는 이유는 다음 반복을 진행하므로 1235가 된다. 

결국 방문처리 해제는 해당 자리수를 위한 것이 아니라 반복문이 전부 종료되면 이전 자릿수의 재귀 함수 호출로 돌아갈 것이므로 그곳에서

해당 숫자를 사용하기 위해 해체해주는 것이다.

마지막으로 재귀가 진행될때마다 자릿수에 중복 없이 저장될 숫자를 저장할 배열을 자리수 크기만큼 만들어둔다.

재귀 함수의 종료 조건은 자릿수가 넘치면 종료된다.

배열은 index가 0부터 시작하므로 자릿수가 넘치는 경우는 각 숫자를 저장한 배열의 index가 M 자릿수가 될 때이다.

재귀 함수를 종료시키며 이때 숫자를 저장해두었던 배열을 출력한다.

구현