들어가며
해당 문제집을 풀면서 주춤했던 문제를 위주로 포스팅한다.
테트로미노는 오늘부로 3번째 푸는 문제이다.
이 문제의 핵심은 뻐큐모양(ㅗ ㅏ ㅜ ㅓ) 을 어떻게 접근하는가이다.
1년전 코테를 위한 알고리즘 공부를 처음할 때는 가볍게 완패하고 함께 공부하는 분의 코드를 보고 개쩌는데.. 싶었다.
두번째로 풀 때는 3달 전인데, 앗 그문제 !! 하면서 시도했지만 도무지 떠오르지 않아 덕분에 여러가지의 풀이가 나왔다.
이번에도 마주한 이 문제는 한번에 접근 방법이 떠오르지 않았고, 20분정도 고민하다 떠올렸다. 그리고 이 인사이트를 남기고 비슷한 문제에 다신 고민하지 않을 것이다.
문제
- 백준 테트로미노
- 난이도: 골드4
- 흔한 dfs로 구현할 수 있는 문제이고, 말했다시피 관건은 뻐큐모양을 처리하는 일이다.
- map을 탐색하며 지나온 칸을 카운팅하며 4개가 되었을 때 값을 갱신한다.
첫번째 풀이
접근 방향
- 인풋이 500*500*(4^3) 정도이므로 브루트포스로 완전탐색하며 한 칸당
dfs를 진행했다. visited방문배열을 두어 지나오지 않은 부분을 지나가며 풀게 했다.- 여기서
cnt==2일 때는 뻐큐모양을 위해, 왔던 길을 다시 지나야 한다.- 이 때 다음 칸으로 이동하지 않고, 현재칸에서 한번 더 탐색할 수 있도록 구현했다.
아래 코드가 핵심이다.
visited[nr][nc] = true;
dfs(nr, nc, cnt + 1, sum + map[nr][nc]);
if (cnt == 2) dfs(r, c, cnt + 1, sum + map[nr][nc]);
visited[nr][nc] = false;통과 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, maxSum;
static int[][] map;
static boolean[][] visited;
static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
static void dfs(int r, int c, int cnt, int sum) {
if (cnt == 4) {
maxSum = Math.max(sum, maxSum);
return;
}
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if (visited[nr][nc]) continue;
visited[nr][nc] = true;
dfs(nr, nc, cnt + 1, sum + map[nr][nc]);
if (cnt == 2) dfs(r, c, cnt + 1, sum + map[nr][nc]);
visited[nr][nc] = false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = 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++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visited[i][j] = true;
dfs(i, j, 1, map[i][j]);
visited[i][j] = false;
}
}
System.out.println(maxSum);
}
}결과
두번째 풀이
접근 방향
이건 '현재 칸에서 한 번 더 탐색한다' 라는 방법이 전혀 떠오르지 않아서 이것저것 떠올리다가 시도했던 방법들.
- 위의 풀이와 유사하지만 cnt=2 일 때, 현재 칸에서 한칸을 더 선택한는 방법이다.
dfs 코드
private static void dfs(int r, int c, int cnt, int sum) {
if (cnt == 4) {
max = Math.max(max, sum);
return;
}
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= M || visited[nr][nc]) continue;
visited[nr][nc] = true;
dfs(nr, nc, cnt + 1, sum + map[nr][nc], visited);
visited[nr][nc] = false;
//뻐큐 고려 - 현재 칸(r,c)에서 하나 더 선택한다
if(cnt == 2) {
for (int dd = 0; dd < 4; dd++) {
// 여기서 방금 위에서 다녀왔던 d 방향이면 넘어가게 해서 나머지 두 곳을 다녀오게 함.
if(dd == d) continue;
int nnr = r + dr[dd];
int nnc = c + dc[dd];
// cnt가 1,2일때 지나온 부분이 나와도 패스
if (nnr < 0 || nnr >= N || nnc < 0 || nnc >= M || visited[nnr][nnc]) continue;
dfs(nr, nc, cnt+2, sum + map[nr][nc] + map[nnr][nnc]);
}
}
}
}결과
코드는 좀 멍청할 수 있지만 효율성은 별 차이 없다.
세번째 풀이
접근 방향
이건 아예 뻐큐구간을 나눠 생각했다.
처음 선택한 (i, j) 좌표에서 뻐큐 구간은 십자 모양 중 3부분만 선택하면 되는 조합 문제 처럼 생각하고 구현한 풀이.
이 메서드가 핵심이다.
백트래킹에서 조합문제를 풀 때 자주 보던 코드이다.
private static void comb(int r, int c, int idx, int cnt, int sum) {
if (cnt == 3) {
max = Math.max(max, sum);
return;
}
for (int i = idx; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
// 선택한 구간을 더한다.
comb(r, c, i + 1, cnt + 1, sum + map[nr][nc]);
}
}조합 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M, max;
static int[][] map;
static boolean[][] visited;
static final int[] dr = {-1, 0, 1, 0};
static final int[] dc = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visited[i][j] = true;
// 브루트포스 - dfs
dfs(i, j, 1, map[i][j]);
visited[i][j] = false;
//뻐큐 모양 체크: 4방향 중에 3개를 골라
comb(i, j, 0, 0, map[i][j]);
}
}
System.out.println(max);
}
private static void dfs(int r, int c, int cnt, int sum) {
if (cnt == 4) {
max = Math.max(max, sum);
return;
}
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= M || visited[nr][nc]) continue;
visited[nr][nc] = true;
dfs(nr, nc, cnt + 1, sum + map[nr][nc]);
visited[nr][nc] = false;
}
}
private static void comb(int r, int c, int idx, int cnt, int sum) {
if (cnt == 3) {
max = Math.max(max, sum);
return;
}
for (int i = idx; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
// 선택한 구간을 더한다.
comb(r, c, i + 1, cnt + 1, sum + map[nr][nc]);
}
}
}결과
역시나 효율성은 비슷하다.
마치며
위의 문제집을 보면 비트마스킹으로도 풀 수 있다고 한다.
비트 마스킹은 넘어가도록 한다..
기간을 두고 세 번이나 시도해도 기억에서 희미해진 것을 보여주는 예시.
해답을 보고 당시에 알았다고 내 것이 아님을 증명해준다.
더불어 문제를 여러 방향으로 구현만 해내면 되는 코테의 세계에서 쫄지말고 시간 복잡도가 허용범위라면 일단 고 하는 거다..
이미 첫번째코드로 일 년 전에 풀었던 걸 얼핏 알면서도 떠오르지 않아 조합을 써서 풀면서도 계속 '아 이렇게 푸는게 아닌데 ..' 라고 생각했다.
그렇다고 안풀고 있으면 안된다. 덕분에 다양한 나만의 풀이를 끄집어낼 수 있었다.
그리고 마침내 원하던 방향으로 접근해서 구현해냈을 때는 참 뿌듯하다. 😋
개발의, 개발에 의한, 개발을 위한 기록장