백준_14500 테트로미노(자바) / 구현 & DFS

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class back_14500_2 {

	static int N,M,ans;
	static int [][] map;
	static boolean[][] visited;
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	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];
		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++) {
				dfs(i,j,0,0);
				dfsOther(i,j);
			}
		}
		System.out.println(ans);
	}

	//한붓 그리기 가능한 경우
	private static void dfs(int i, int j,int dep, int sum) {
		if(dep==4) {
			ans = Math.max(ans, sum);
			return;
		}
		
		for (int k = 0; k < 4; k++) {
			int xx = dx[k]+i;
			int yy = dy[k]+j;
			if(xx<0||yy<0||xx>=N||yy>=M||visited[xx][yy])continue;
			
			visited[xx][yy]=true;
			dfs(xx,yy,dep+1,sum+map[xx][yy]);
			visited[xx][yy]=false;
		}
	}
	
	//한붓 그리기 불가능한 경우
	private static void dfsOther(int i, int j) {
		int total = 4;
		int sum = map[i][j];
		int min = Integer.MAX_VALUE;
		for (int k = 0; k < 4; k++) {
			if(total<3)return;
			
			int xx = dx[k]+i;
			int yy = dy[k]+j;
			
			if(xx<0||yy<0||xx>=N||yy>=M) {
				total--;
				continue;
			}
			
			min = Math.min(min, map[xx][yy]);
			sum+=map[xx][yy];
		}
		
		if(total==4) {
			sum -=min;
		}
		ans=Math.max(sum, ans);
	}
	
}

 

 

※ 내 생각

이 문제는 이어붙힐수 있는 정사각형 4개의 최댓값을 구하는 문제입니다.

처음에는 DFS로 4칸에 대한 최댓값을 구했는데 실패했습니다.
생각해보니 한붓그리기가 불가능한 경우도 있었습니다.

따라서 이 문제는 한붓그리기가 가능한 경우와 한붓그리기가 불가능한 경우를 따져가며 풀어야 하는 문제입니다.

한붓그리기가 가능한 경우는 DFS를 이용해서 풀이를 진행하면 되고,
불가능한 경우에는 직접 구현해서 문제풀이를 했습니다.

풀이는 어렿지 않으나, 한붓그리기가 불가능한 경우를 생각하는게 어려웠던 문제였습니다.