문제 탐색하기
입력 자료 정리
- n은 나무 재료의 세로 크기, m은 나무 재료의 가로 크기다
- 그다음 들어오는 값들은 각 나무 재료 한 칸의 원소값이다
해결방법 추론
- n,m이 둘다 5이기 때문에 백트래킹으로 쉽게 해결할 수 있을 것이라 생각하였다
- 백트래킹을 하면서 그 합을 리스트에 저장하고 내림차순 하여 첫번째 값을 출력한다면
정답이 될 것이다 - 나무재료를 n x m만큼 탐색하면서 4개의 모양을 각각 선택했을 때도
백트래킹으로 돌려보면 모든 경우에 대해 탐색할 수 있다
시간복잡도 계산
- 시간복잡도는 n x m 만큼 탐색하면서 추가로 4개의 모양을 더 살펴봐서 n x m x 4의 연산이 발생한다
- 이어서 이것을 백트래킹으로 진행하는데, 모양이 총 3칸이므로 n x m / 3만큼 추가 탐색을
하게 될 것이다 - 정리하면 n x m x 4 연산을 (nxm)/3 만큼 동안 하게 된다
- 따라서 시간복잡도는 O((nxmx4)^((nxm)/3))이 되고 놀랍게도 최대 천만의 연산이 나와서
시간제한에 걸리지 않고 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리하기
- n x m크기의 2차원 배열로 각 입력값들을 관리해준다
- 방문 배열도 똑같은 크기로 만들어주며, 정답을 관리할 리스트 배열도 하나 만들어준다
백트래킹 설계
함수식
- void backtracking(int n, int m, int sum, int start);
1. 모든 좌표 탐색을 위해 n과 m을 파라미터로 넘겨주며, 누적된 합산을 관리하는 sum 파라미터와
다음 좌표로의 이동을 위해 start 파라미터도 만들었다
재귀식
- backtracking(n,m,sum+tmp, i+1)
1. 3개의 좌표의 합산을 인수로 넘겨주며, 다음 탐색값을 i+1로 넘겨준다
base condition
- 없음
1. 놀랍게도 base condition은 존재하지 않는다.
왜냐하면, 다음 조건을 만족하지 못하면 아예 재귀식을 실행하지 않도록 설계했기 때문이다
2. 인덱스 범위를 벗어나거나 나무 재료의 주어진 모양에서의 3개 영역을 하나라도 방문했다면
재귀식을 실행하지 않는다
3. 따라서 n x m만큼의 순회가 일어나면 재귀식이 알아서 종료되어서
따로 base condition을 만들어줄 필요가 없다
내부 로직 설계
- 리스트에 sum을 어떻게 넣을 수 있을까 의문이 들 것이다
- 문제를 잘 생각해보면 모양 하나만으로도 정답이 될 수도 있다
- 이점을 고려한다면 함수식이 실행될때마다 sum을 리스트에 넣는다면 문제를 해결할 것이라고
충분히 생각할 수 있다 - 따라서 함수식이 실행되는 맨 처음에 리스트에다가 sum을 넣어주며,
이렇게 했을 때 0이 무조건 들어가게 되어서 탐색값이 하나도 들어가지 않았을 때
정렬 후 그냥 첫번째 값을 출력하면 된다 - 앞선 넴모넴모 문제에서 사용했던 방식으로 2차원 배열을 이중포문이 아닌 하나의 포문으로
탐색하도록 하였다 - 세로좌표는 나무재료의 가로길이인 m으로 i를 나눈 몫이며,
가로좌표는 나무재료의 가로길이인 m으로 i를 나눈 나머지다. - 이어서 4개의 모양을 모두 탐색해야하는데 if문으로 분기를 4개 나눠서 하는 방법도 있지만
가독성을 좀 높이고 중복 코드도 줄이기 위해 bfs 탐색에서 사용하는 dy, dx 배열을 활용하였다 - 이 방법을 사용할 수 있는 이유는 각 모양을 봤을 때,
중심지점을 기점으로 y값만 변하는 지점과 x값만 변하는 지점 2개만 존재하기 때문이다 - 따라서 해당 배열을 사용하여 미리 세팅해둔 뒤, 탐색을 한다
- 3개의 값을 합산해둘 임시 변수 tmp와 새로운 세로 좌표와 가로 좌표인 ny, nx를 변수로
선언하여 각각 초기화해둔다 - 이어서 인덱스 범위를 ny, nx가 벗어나지 않으면서, 모양의 각 위치를 탐색하지 않았따면
중심 지점은 2배만큼 더해주고 나머지는 그냥 더해준다 - 백트래킹 기법을 이용하여 재귀식 전에 방문 체크, 이후 방문 해제를 하는데
3개의 지점 모두에 백트래킹 기법을 적용한다 - 이어서 재귀식을 실행하면 정상적으로 로직이 작동된다
출력 설계
- 완성한 리스트를 내림차순 정렬해준다
- 이제 리스트의 첫번째 인덱스의 값을 출력하면 정답이 된다.
정답 코드
import java.io.*;
import java.util.*;
public class Main {
static int[][] arr;
static List<Integer> lists = new ArrayList<>();
static boolean[][] visited;
static int[] dy = {1, -1, -1, 1};
static int[] dx = {-1, -1, 1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
backtracking(n,m,0, 0);
lists.sort(Collections.reverseOrder());
bw.write(lists.get(0)+"");
br.close();
bw.close();
}
private static void backtracking(int n, int m, int sum, int start) {
lists.add(sum);
for (int i = start; i < n * m; i++) {
int r = i / m;
int c = i % m;
for (int j = 0; j < 4; j++) {
int tmp = 0;
int ny = dy[j] + r;
int nx = dx[j] + c;
if(ny >= 0 && nx >= 0 && ny < n && nx < m && !visited[r][c] && !visited[ny][c] && !visited[r][nx]){
tmp += arr[r][c]*2;
tmp += arr[ny][c];
tmp += arr[r][nx];
visited[r][c] = true;
visited[ny][c] = true;
visited[r][nx] = true;
backtracking(n,m,sum + tmp, i+1);
visited[ny][c] = false;
visited[r][nx] = false;
visited[r][c] = false;
}
}
}
}
}문제 링크
Software Developer