[SWEA][DFS][Java] 2819. 격자판의 숫자 이어 붙이기 : D4 (feat. 메모리 절반 줄이기)

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB

SW Expert Academy

 

이번 글에서는 SWEA 2819 - 격자판의 숫자 이어 붙이기 문제를 DFS로 해결한 과정과, 문자열 처리 방식 개선을 통해 메모리 사용량을 크게 줄인 경험을 정리해보려고 한다.

 

문제를 처음 풀었을 때는 단순히 DFS를 이용해 숫자를 이어 붙이고, 중복을 제거하기 위해 HashSet을 사용하는 방식으로 접근했다. 하지만 이후 문자열 처리 방식을 개선하면서 메모리 사용량이 절반 가까이 줄어드는 것을 확인할 수 있었다.

 

문제 접근 방법

문제는 4×4 격자에서 시작 위치를 하나 정한 뒤 상하좌우로 이동하면서 숫자를 이어 붙여 7자리 숫자 문자열을 만드는 것이다.

같은 칸을 여러 번 방문할 수 있다!! 이거시 핵심..

1. 모든 격자 칸을 시작점으로 설정
2. DFS로 상하좌우 이동하며 숫자를 이어 붙임
3. 깊이가 7이 되면 하나의 숫자 완성
4. Set에 넣어 중복 제거

DFS 깊이는 최대 7이고 이동 방향은 4개이므로 탐색 수는 대략 다음과 같다.

16 * 4^6 ≈ 65536

 

충분히 완전 탐색이 가능한 수준이다.

 

 

1. 첫 번째 풀이는 문자열 누적 방식이였다. 

처음에는 DFS에서 문자열을 계속 이어 붙이는 방식으로 구현했다.

핵심 코드는 다음과 같다.

dfs(ni, nj, depth+1, str + Integer.toString(arr[ni][nj]));

 

현재 문자열 뒤에 숫자를 붙여 다음 DFS로 전달하는 방식이다.

이 방식은 구현이 직관적이라는 장점이 있지만, 내부적으로는 상당한 비용이 발생한다.

왜냐하면 Java에서 String은 immutable(불변 객체) 이기 때문이다.

즉 위 코드가 실행될 때, 1) 새로운 String 객체 생성 2) 기존 문자열 복사 3)새 문자 추가 과정이 매번 발생한다.

DFS 탐색 과정에서 수만 번의 문자열 생성이 일어나기 때문에 불필요한 객체가 매우 많이 만들어진다.

결과적으로, 메모리 사용량 증가와 GC(Garbage Collection) 부담이 증가한다. 

2. 개선 아이디어

문자열을 매번 새로 생성하는 대신 재사용 가능한 배열을 사용하면 어떨까라는 생각이 들었다.

숫자의 길이는 항상 7자리로 고정되어 있다. 즉 문자열 길이를 미리 알고 있기 때문에 char 배열 하나만 만들어 DFS 동안 재사용할 수 있다.

 

 

이번 문제를 통해 느낀 점은 다음과 같다.

1. 문자열을 계속 생성하는 것은 생각보다 비용이 크다
2. 길이가 고정된 문자열이라면 배열을 활용하는 것이 효율적이다
3. 완전 탐색 문제에서는 객체 생성 비용도 중요한 최적화 포인트가 될 수 있다

특히 코딩 테스트에서는 문제를 풀기만 하는 것뿐 아니라 메모리 사용과 객체 생성 비용까지 고려한 구현이 필요하다는 점을 다시 한번 느낄 수 있었다.

개선 전 코드

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

import java.util.Set;
import java.util.HashSet;
class Solution
{
    static int[][] arr;
    static Set<String> s;
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int test_case = 1; test_case <= T; test_case++)
        {
            sb.append("#").append(test_case).append(" ");

            s = new HashSet<>();

            arr = new int[4][4];
            for(int i = 0; i < 4; i++){
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < 4; j++){
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            for(int i = 0; i <4; i ++){
                for(int j = 0; j<4; j++){
                    String str = Integer.toString(arr[i][j]);
                    dfs(i,j,1, str);
                }
            }

            sb.append(s.size()).append("\n");
        }
        System.out.print(sb);
    }

    public static void dfs(int i, int j, int depth, String str){
        if(depth == 7){
            s.add(str);
            return;
        }

        for(int a = 0; a < 4; a++){
            int ni = i + dx[a];
            int nj = j + dy[a];

            if(ni < 0 || ni >= 4 || nj <0 || nj >= 4)
                continue;
            
            dfs(ni, nj, depth+1, str + Integer.toString(arr[ni][nj]));
        }
    }
}

개선 후 코드

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

import java.util.Set;
import java.util.HashSet;
class Solution
{
    static int[][] arr;
    static Set<String> s;
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int test_case = 1; test_case <= T; test_case++)
        {
            sb.append("#").append(test_case).append(" ");

            s = new HashSet<>();

            arr = new int[4][4];
            for(int i = 0; i < 4; i++){
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < 4; j++){
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            for(int i = 0; i <4; i ++){
                for(int j = 0; j<4; j++){
                    char[] result = new char[7];
                    result[0] = (char) (arr[i][j] + '0');
                    dfs(i,j,1, result);
                }
            }

            sb.append(s.size()).append("\n");
        }
        System.out.print(sb);
    }

    public static void dfs(int i, int j, int depth, char[] result){
        if(depth == 7){
            s.add(String.valueOf(result)); 
            return;
        }

        for(int a = 0; a < 4; a++){
            int ni = i + dx[a];
            int nj = j + dy[a];

            if(ni < 0 || ni >= 4 || nj <0 || nj >= 4)
                continue;
            
            result[depth] = (char) (arr[ni][nj] + '0');
            dfs(ni, nj, depth+1,  result);
        }
    }
}