박시은

(❁´◡`❁)

5 분 소요


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


📌 문제

문제 유형

  • 구현
  • 브루트포스


📘 문제 설명


📥 입력

  • 첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
  • 둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다.
  • i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다.
  • 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.
5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1

📥 출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

19



🔍 문제 풀이

문제 해결 절차

  1. DFS로 연속된 4칸을 탐색하며 최대값을 찾는다.
  2. DFS로 만들 수 없는 ㅗ, ㅏ, ㅜ, ㅓ 모양은 별도로 시뮬레이션 처리를 하여 최대값을 찾는다.


어떤 알고리즘을 사용해야 할까?

이 문제에서는 모든 칸에서 시작해, 상하좌우로 4칸을 탐색해야 하므로 DFS(깊이 우선 탐색) + 백트래킹이 가장 적합하다.

  • DFS (깊이 우선 탐색)

    • 한 방향으로 끝까지 들어간 뒤, 막히면 뒤로 돌아오는 방식 (Backtracking)
    • 재귀 기반 -> 백트래킹 가능

  • BFS (너비 우선 탐색)

    • 현재에서 가까운 모든 위치를 먼저 탐색
    • 큐 기반 -> 레벨 단위 탐색 -> 중간 분기 어려움


아래 그림은 DFS와 BFS가 탐색하는 순서를 비교한 것이다.

테트로미노

위 그림을 통해 BFS는 가능하긴 하나, 큐 상태에서 깊이 추적이 어렵다는 것을 확인할 수 있다.

따라서 가까운 칸부터 넓게 탐색하는 BFS보다, 한 방향으로 깊게 탐색하는 DFS가 더 적합하다.


단, ‘ㅗ’, ‘ㅜ’, ‘ㅏ’, ‘ㅓ’ 모양 도형은 DFS로 만들 수 없다.

  • DFS는 한 방향으로만 계속 탐색하기 때문에, 중간에서 양쪽으로 분기하는(3방향으로 퍼지는) 구조를 만들 수 없다.
  • 그럼 어떻게 처리해야할까? 알아보자.


‘ㅗ’모양은 어떻게 처리하지?

‘ㅗ’, ‘ㅏ’, ‘ㅜ’, ‘ㅓ’ 모양 도형은 상하좌우 탐색으로는 불가능하다.

따라서 checkTShape(x, y) 함수를 통해 현재 좌표 (x, y)를 중심으로 3방향을 더해 ㅗ 모양 도형을 만들 수 있도록 해줬다.

방향 좌표 변화
왼쪽 x, y - 1
오른쪽 x, y + 1
위쪽 x - 1, y
아래쪽 x + 1, y 
int[][] Tshapes = {
    {0, -1, -1, 0, 0, 1}, // ㅗ
    {-1, 0, 0, 1, 1, 0}, // ㅏ
    {0, -1, -1, 0, 1, 0}, // ㅓ
    {0, -1, 0, 1, -1, 0} // ㅜ
};

테트로미노2

  • 이처럼, 중심 좌표 (x, y)를 기준으로 양 방향으로 뻗어나가도록 해야 한다.
  • 즉, 중심 좌표를 기준으로 3개의 방향으로 확장하여 총 4칸을 구성하는 방식이다.


예를 들어 ㅗ 모양의 경우:

  • 중심: (x, y)
  • 확장: 왼쪽 (x, y - 1), 오른쪽 (x, y + 1), 아래 (x + 1, y)

이러한 방식으로 ㅏ, ㅓ, ㅜ, ㅗ 총 4가지 모양을 구현할 수 있다.

이처럼 모든 칸에서 모든 방향의 도형을 직접 시도하여 누적 최대값을 찾는다.



📌 놓친 점

dfs() 함수 내부에서 visited[x][y] = true를 바로 해줬는데,
왜 굳이 main() 함수에서 시작 좌표에 대해 먼저 방문 처리를 해줘야 할까? 이해가 가지 않았다.

하지만,

  • DFS는 재귀를 통해 “다음 위치”들을 탐색하는 함수이기 때문에,
  • 시작 좌표 (i, j)는 DFS가 호출되기 전에 방문처리를 해줘야 해당 위치가 중복으로 사용되는 것을 방지할 수 있다.
  • 즉, 하나의 경로가 끝나고 나면, 그 위치를 다시 쓸 수 있도록 visited = false로 풀어줘야 한다.


dfs() 내부에서 처리하는 잘못된 경우의 예시이다.

static void dfs(int x, int y, int depth, int sum) {
    visited[x][y] = true; // 이미 dfs 호출됨. 너무 늦음
    ...
}
  • 이 방식은 DFS 내부에 진입하고 나서야 방문 처리되므로,
  • 이미 다른 경로에서도 (x, y)를 사용할 가능성이 생긴다.
  • 즉, (i, j)에서 시작하는 다른 경로에서 이 좌표를 사용할 수도 있는 것이다.
  • 특히 백트래킹 구조에서는 이게 중복 탐색의 원인이 된다.


따라서 아래와 같이 main() 함수에서 처리해야한다.

visited[i][j] = true; // 시작점 직접 방문 처리
dfs(i, j, 1, graph[i][j]);
visited[i][j] = false;  // 탐색 후 백트래킹
  • 위처럼 시작 지점은 DFS 진입 전에 방문 처리를 해야
  • DFS 내부에서도, 다른 경로에서도 처음 좌표가 중복해서 사용되는 것을 방지할 수 있다.


정리하자면,

  • 시작점을 dfs() 내부에서 방문처리를 하면 -> 진입 전에 중복 탐색 가능성이 생김
  • main()에서 시작점 방문처리를 하면 -> 중복 없이 한 번만 탐색 가능



💻 전체 코드

import java.io.*;
import java.util.*;

public class Main {
    static int  n, m;
    static int[][] graph;
    static boolean[][] visited;
    static int max = Integer.MIN_VALUE;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

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

        for(int d=0; d<4; d++){
            int nx = x + dx[d];
            int ny = y + dy[d];

            if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
            if(!visited[nx][ny]){
                visited[nx][ny] = true;
                dfs(nx, ny, depth+1, sum + graph[nx][ny]);
                visited[nx][ny] = false; // 백트래킹
            }
        }
    }

    // 'ㅗ'모양 처리 함수
    public static void checkTShape(int x, int y) {
        // x와 y는 중심좌표 여기에 3개를 더해서 ㅗ, ㅜ, ㅏ ,ㅓ 모양 만들기
        int[][] cases = {
                //dx1, dy1, dx2, dy2, dx3, dy3 (중심(x,y) 기준 3칸의 상대 좌표)
                {-0, -1, -1, 0, 0, 1}, // ㅗ
                {-1, 0, 0, 1, 1, 0}, // ㅏ
                {0, -1, -1, 0, 1, 0}, // ㅓ
                {0, -1, 0, 1, 1, 0} //ㅜ

        };

        for (int[] c : cases) {
            int x1 = x + c[0], y1 = y + c[1];
            int x2 = x + c[2], y2 = y + c[3];
            int x3 = x + c[4], y3 = y + c[5];

            if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) continue;
            if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m) continue;
            if (x3 < 0 || x3 >= n || y3 < 0 || y3 >= m) continue;

            int sum = graph[x][y] + graph[x1][y1] + graph[x2][y2] + graph[x3][y3];
            max = Math.max(max, sum);
        }
    }

    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());

        graph = 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++){
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<n; i++){ // 모든 칸 탐색 시작
            for(int j=0; j<m; j++){
                visited[i][j] = true;
                // 현재 칸도 포함했기 때문에 depth = 1
                // graph[i][j]는 현재 칸의 숫자 합
                dfs(i, j, 1, graph[i][j]);
                visited[i][j] = false; // DFS 끝나고, 다음 위치에서 다시 쓸 수 있도록 방문 해제


                checkTShape(i, j); // 'ㅗ' 모양 처리
            }
        }
        System.out.println(max);
    }
}


이로써 class 3 문제 해결 완료! 🤗


카테고리:

업데이트:

댓글남기기

참고