이번에 풀어본 문제는
백준 14500번 테트로미노 입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int [][] map;
static int [] dx = {0,0,1,-1};
static int [] dy = {1,-1,0,0};
static int [][] ex = {{0,0,-1},{0,0,1},{0,-1,1},{-1,1,0}}; // ㅗ ㅜ ㅓ ㅏ
static int [][] ey = {{-1,1,0},{-1,1,0},{-1,0,0},{0,0,1}};
static boolean [][] isVis;
static int n,m;
static int maxVal = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer 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());
}
}
isVis = new boolean[n][m];
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
isVis[i][j] = true;
dfs(i,j,1,map[i][j]);
isVis[i][j] = false;
getElse(i,j);
}
}
System.out.print(maxVal);
}
static void dfs(int x, int y,int cnt,int val)
{
if(cnt == 4)
{
maxVal = Math.max(maxVal,val);
return;
}
for(int idx = 0; idx < 4; ++idx)
{
int mx = x + dx[idx];
int my = y + dy[idx];
if(!isValid(mx,my) || isVis[mx][my]) continue;
isVis[mx][my] = true;
dfs(mx,my,cnt+1,val+map[mx][my]);
isVis[mx][my] = false;
}
}
static boolean isValid(int x, int y)
{
return x >= 0 && y >= 0 && x < n && y < m;
}
static void getElse(int x, int y)
{
next : for(int i = 0; i < 4; ++i)
{
int res = map[x][y];
for(int j = 0; j < 3; ++j)
{
int mx = x + ex[i][j];
int my = y + ey[i][j];
if(!isValid(mx,my)) continue next;
res += map[mx][my];
}
maxVal = Math.max(maxVal,res);
}
}
}
먼저 dfs로 풀이를 해보았지만 (ㅗ,ㅜ,ㅓ,ㅏ) 모양은 dfs로 탐색이 불가능하기 때문에, 별도로 해당 모양을 탐색할 2차원 배열을 만들어서 추가적으로 탐색해주었습니다.
흔한 dfs문제와 흐름이 같고, getElse 함수로 모양을 만들 수 있을경우 추가적으로 최댓값을 비교하여 갱신해주도록 합니다.
이전에 풀었던 칠공주 문제처럼 조합을 이용할까 했지만, 최대 크기가 500이라서
25000개중에 4개를 택하는 모든 조합을 구하면.... 안되겠더라구요ㅋㅋㅋㅋㅋ
처음에 dfs를 돌기 전마다 방문배열을 초기화해줬더니 시간초과 떴습니다;
평소 초기화 위치는 크게 신경 안썼었는데, 이번에 대체 왜??! 하며 곰곰히 찾다보니 사소하게 넘어갔던 부분에서 또 하나 배워갑니다!
월급 루팡중인 동기가 골라준 문제인데,뭔가 알록달록 접근부터 흥미로운 문제였습니다 😀ㄱㅅ