14500 테트로미노 - 삼성 sw 역량 기출

테트로미노

1. ㅗ 모양을 제외한 것들은 dfs로 합계 구할 수 있음
   

idx == 4이면 최대값 리턴

시간초과 : visited배열을 계속 생성하는 것이아닌 백트래킹 방식으로 static으로 배열을 생성해 놓고 사용하니 해결됨

​

1. ㅗ 모양은 따로 함수를 만들어서 가운데 칸을 기준으로 회전하는 4개 중 최대값을 리턴하는 함수를 만든다
   

맵보다 큰 것을 검사할 때 한번에 제외하지 않고 현재 비교하는 모양일 때만 검사

조건에 맞는 것도 확인을 안하는 경우도 있었음

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

public class Main테트로미노 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());

		map = new int[N][M];

		for(int i = 0; i < N; i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st2.nextToken());
			}
		}
		ans = 0;
		visited = new boolean[N][M];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				dfs(i, j, 0, 0);
				nodfs(i, j);
			}
		}
		System.out.println(ans);
	}
	static int ans;
	static int[][] map;
	static int N;
	static int M;
	static int[] dx = { 0, 0, -1, 1};
	static int[] dy = { 1, -1, 0, 0};
	static boolean[][] visited;
	static void dfs(int y, int x, int idx, int sum) {
		if(idx == 4) {
			ans = Math.max(ans, sum);
			return;
		}
		sum+=map[y][x];
		visited[y][x] = true;
		for(int i = 0; i < 4; i++) {
			int yi = y + dy[i];
			int xi = x + dx[i];

			if(yi < 0 || xi < 0 || yi >= N || xi >= M)continue;

			if(!visited[yi][xi]) {
				dfs(yi, xi, idx+1, sum);
			}
		}
		visited[y][x] = false;
	}

	static void nodfs(int y, int x) {

		if(x + 1 < M && y-1 >= 0 && x-1 >= 0) {
			ans = Math.max(ans, map[y-1][x] + map[y][x-1] + map[y][x+1] + map[y][x]);
		}
		if(y+1 < N && x + 1 < M && y-1 >= 0) {
			ans = Math.max(ans, map[y-1][x] + map[y][x+1] + map[y+1][x] + map[y][x]);
		}
		if(y-1 >= 0 && y+1 < N && x-1 >= 0) {
			ans = Math.max(ans, map[y-1][x] + map[y+1][x] + map[y][x-1] + map[y][x]);
		}
		if(x-1 >= 0 && x+1 < M && y+1 < N) {
			ans = Math.max(ans, map[y][x-1] + map[y][x+1] + map[y+1][x] + map[y][x]);
		}


	}
}