이번에 풀어본 문제는
백준 3085번 사탕 게임 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

class Point
{
    int x,y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int N;
    static char [][] map;
    static int [] dx = {0,1};
    static int [] dy = {1,0};
    static int max = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        map = new char[N][N];

        for(int i = 0; i < N; ++i)
        {
            String tmp = br.readLine();
            map[i] = tmp.toCharArray();
        }


        for(int i = 0; i < N; ++i)
        {
            for(int j = 0; j < N; ++j) find(i,j,map[i][j]);
        }
        System.out.println(max);
    }
    static void find(int x, int y, char color)
    {
        for(int idx = 0; idx < 2; ++idx)
        {
            int mx = x + dx[idx];
            int my = y + dy[idx];

            if(!isValid(mx,my)) continue;
            if(map[mx][my] != color)
            {
                char nextColor = map[mx][my];
                map[x][y] = nextColor;
                map[mx][my] = color;
                check();
                map[x][y] = color;
                map[mx][my] = nextColor;
            }
        }
    }

    static void check()
    {
        for(int i = 0; i < N; ++i)
        {
            //행
            eat(i,0,0);
            //열
            eat(0,i,1);
        }

    }
    static void eat(int x, int y,int dir)
    {
        int cnt = 1;
        char color = map[x][y];

        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x,y));
        while(!q.isEmpty())
        {
            Point cur = q.poll();

            int mx = cur.x + dx[dir];
            int my = cur.y + dy[dir];

            if(!isValid(mx,my)) return;

            if(map[mx][my] != color)
            {
                color = map[mx][my];
                cnt = 1;
                int afterLen = N - (x+y+1);
                if(afterLen <= max) return;
            }
            else
            {
                cnt++;
                max = Math.max(max,cnt);
            }
            q.add(new Point(mx,my));

        }
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < N && y < N;
    }

}

📝 풀이

각자 다른 색상을 가진 사탕들이 맵으로 주어질 때, 인접한 사탕의 위치를 한 번 변경할 수 있습니다. 행,열 마다 일자로 연결된 사탕을 연속하여 먹을 수 있다고 할 때, 가장 많은 사탕을 먹을 수 있는 최댓값을 구하는 문제입니다.
완전탐색으로 풀어보았습니다.
보통 이런 경우 원본 맵을 보존하기 위해 복사하여 사용하곤 하는데, 이 문제의 경우에는 위치 변경을 1회만 하기 때문에, 변경한 상태로 맵을 탐색하고, 다시 돌려놓는 방법을 사용했습니다.
find 함수는 변경할 사탕을 탐색하는 함수입니다. 처음에는 상하좌우 모두 탐색하면서 탐색의 중심이 된 인덱스를 방문 체크하는 방법을 사용했습니다. 하지만 풀면서 생각해보니 탐색 범위를 우측과 하단 두가지만 선택한다면 방문배열 없이 모든 경우의 수를 탐색할 수 있었고, 좀 더 효율적으로 탐색할 수 있었기 때문에 변경했습니다. 위 방식으로 인접한 사탕중 색이 다른 사탕이 존재한다면, 두 사탕의 위치를 변경한 후 check 함수로 현재 맵의 상태를 기준으로 max값을 갱신해준 후, 원상복구 시킵니다.
위와같은 방법으로 모든 인덱스에서 find함수를 수행하게 되면 최댓값을 구할 수 있습니다.

📜 후기

딱히 예외를 고려하지 않고 있는 그대로 불필요한 모든 경우의 수까지 탐색하다 보니 메모리 초과가 발생했습니다. 다시 차근차근 읽어보면서 최적화를 진행하여 해결할 수 있었습니다.