[BOJ 14500] 테트노미로

문제출처

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

 

문제풀이

N x M 배열에 테트리스 도형들을 적절히 회전하여 1개를 놓았을때 놓인 칸들의 최대 합을 구하는 문제입니다.

삼성 기출문제답게 map위에서 동,북,서,남 방향으로 탐색해서 풀이하면 될것이라 생각했지만 'ㅜ'모양은 기존 dfs와 다른 방식으로 탐색해야했습니다.

'ㅜ' 모양을 탐색하는 제 아이디어는 다음과 같습니다.

 

1. 해당 위치를 기준으로 동,북,서,남 방향 모두 탐색하며 map에 저장된 값들을 더한다.

2. 탐색 시 매번 map의 최소값을 구한다.

3. 모두 탐색한 뒤 최소값을 빼준다.

즉, 현재위치 + 4방향 - 4방향중 최소값으로 'ㅜ'모양을 탐색했습니다.

+ 모양으로 탐색한 뒤 가장 최소값을 빼주면 'ㅜ'의 회전체 모양이 나오기 때문입니다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/SW_TEST(samsung)/BOJ_14500/boj14500.java

sw93/algorithm

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

public class Main {
    private static int n, m, ans=0;
    private static int dy[] = {0, -1, 0, 1};
    private static int dx[] = {1, 0, -1, 0};
    private static int map[][];
    private static boolean visit[][];

    public static void main(String[] args) throws Exception {
        init();
        for (int y=0; y<n; y++) {
            for (int x=0; x<m; x++) {
                dfs(y, x, 0, 0);
                checkException(y, x);
            }
        }
        System.out.println(ans);
    }

    private static void dfs(int y, int x, int sum, int count) {
        if (count == 4) {
            ans = Math.max(ans, sum);
            return;
        }

        for (int i=0; i<4; i++) {
            int ny = y+dy[i];
            int nx = x+dx[i];
            if (ny<0 || nx<0 || ny>=n || nx>=m || visit[ny][nx]) continue;
            visit[ny][nx] = true;
            dfs(ny, nx, sum+map[ny][nx], count+1);
            visit[ny][nx] = false;
        }
    }

    private static void checkException(int y, int x) {
        int sum = map[y][x];
        int count = 1;
        int min = 987654321;

        for (int i=0; i<4; i++) {
            int ny = y+dy[i];
            int nx = x+dx[i];
            if (ny<0 || nx<0 || ny>=n || nx>=m) continue;
            sum += map[ny][nx];
            min = Math.min(min, map[ny][nx]);
            count++;
        }

        if (count == 5) {
            sum -= min;
        }
        ans = Math.max(ans, sum);
    }

    private static void init() throws Exception {
        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];
        visit = new boolean[n][m];

        for (int y = 0; y < n; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < m; x++) {
                map[y][x] = Integer.parseInt(st.nextToken());
            }
        }
    }
}