TDD를 알고리즘 문제 풀이에 적용시켜보자

저는 TDD를 공부하던 중 TDD를 이용하여 알고리즘 문제를 풀면 괜찮지 않을까?라는 생각을 하게 되었습니다.

시간은 조금 더 걸리겠지만, TDD의 장점인 내 코드에 대한 피드백이 빠르기 때문에 즉각적으로 제가 잘못 작성한 코드를 알 수 있을 것이라는 기대감을 품고 시작하였습니다. 

결론부터 말씀드리자면 TDD를 알고리즘 문제에 적용시키는 것은 추천드리지 않습니다.

 

2164번 소스코드

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.function.Function;

public class BOJ_2164 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        System.out.println(solution(n));
    }
    public static int solution(int n){
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1 ; i <= n ; i++){
            q.offer(i);
        }
        while(q.size() > 1){
            removeTop(q);
            moveTopToBottom(q);
        }
        return q.peek();
    }
    public static void removeTop(Queue<Integer> q){
        q.poll();
    }
    public static void moveTopToBottom(Queue<Integer> q){
        q.offer(q.poll());
    }
}

2164번 Test코드

package BOJ;

import static org.junit.jupiter.api.Assertions.*;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

class BOJ_2164Test {
    private BOJ_2164 boj_2164;
    @BeforeEach
    void setup(){
        boj_2164 = new BOJ_2164();

    }
    @Test
    @DisplayName("예제 입력")
    void exampleTest(){
        int n = 6;
        assertEquals(4,boj_2164.solution(n));
    }

    @Test
    @DisplayName("1 입력")
    void exampleTestOne(){
        int n = 1;
        assertEquals(1,boj_2164.solution(n));
    }

    @Test
    @DisplayName("10 입력")
    void exampleTestTen(){
        int n = 10;
        assertEquals(4,boj_2164.solution(n));
    }

    @Test
    @DisplayName("4 입력")
    void exampleTestFour(){
        int n = 4;
        assertEquals(4,boj_2164.solution(n));
    }

    @Test
    @DisplayName("removeTopTest")
    void removeTopTest(){
        int n = 6;
        Queue<Integer> deque = new LinkedList<>();
        for(int i = 1 ; i <= n ; i++){
            deque.offer(i);
        }
        boj_2164.removeTop(deque);
        assertEquals(2,deque.peek());
    }

    @Test
    @DisplayName("moveTopToBottomTest")
    void moveTopToBottom(){
        int n = 6;
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1 ; i <= n ; i++){
            q.offer(i);
        }
        boj_2164.moveTopToBottom(q);
        assertEquals(2,q.poll());
        assertEquals(3,q.poll());
        assertEquals(4,q.poll());
        assertEquals(5,q.poll());
        assertEquals(6,q.poll());
        assertEquals(1,q.poll());
    }
}

TDD를 적용시켜 Test코드를 먼저 작성하고 해당 테스트 코드에 대한 소스코드를 작성하려 노력하였습니다.

사실 한 줄 짜리 코드는 딱히 메서드로 뺄 필요는 없어보이지만, 의미를 좀 더 명확하게 하고 Test 코드를 작성하려고 메서드로 만들었습니다. 사실 이때 너무 Test코드에만 집중해서인지 main문을 작성하는 것을 잊고 왜 안되지라는 생각에 빠졌습니다 ..... 😥😥😥

 

사실 여기까지의 생각은 TDD를 적용시켜도 나쁘지 않겠다라는 생각을 하였습니다. 위의 문제는 사실 예외 상황도 별로 없기 때문에 fail에 대한 테스트 코드가 많이 필요하지 않았고 로직도 길지 않아 그렇게 생각하였습니다. 그래서 시뮬레이션나 구현 문제에 대해서도 TDD를 적용시켜보면 괜찮지 않을까라는 생각을 하였습니다. 

다음은 16985번 소스코드와 테스트 코드입니다.

 

16985번 소스 코드

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_16985 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        Function<String,Integer> stoi = Integer::parseInt;
        int[][][] arr = new int[SIZE][SIZE][SIZE];
        for(int k = 0 ; k < SIZE ; k++){
            for(int i = 0 ; i < SIZE ; i++){
                st = new StringTokenizer(br.readLine(), " ");
                for(int j = 0 ; j < SIZE ; j++){
                    arr[k][i][j] = stoi.apply(st.nextToken());
                }
            }
        }
        System.out.println(solution(arr));
    }
    private static final int SIZE = 5;
    private static final int INF = 987654321;
    public static int solution(int[][][] arr){
        boolean[] used = new boolean[SIZE];
        int[][][] board = new int[SIZE][SIZE][SIZE]; // 높이 세로 가로
        int result = dfs(0,used,arr,board);
        if(result == INF){
            return -1;
        }
        return result;
    }
    public static int dfs(int depth,boolean[] used,int[][][]arr,int[][][] board){
        if(depth == SIZE){
            return findRoute(board);
        }
        int result = INF;
        for(int i = 0 ; i < SIZE ; i++){
            if(used[i]){
                continue;
            }
            used[i] = true;
            int[][] temp = new int[SIZE][SIZE];
            copyArr(temp,arr[i]);
            for(int j = 0 ; j < 4; j++){
                temp = rotationBoard(temp);
                copyArr(board[depth],temp);
                result = Math.min(result,dfs(depth+1,used,arr,board));
            }
            used[i] = false;
        }
        return result;
    }

    private static void printArr(int[][] ints) {
        for(int i = 0 ; i < SIZE ; i++){
            for(int j = 0 ; j < SIZE ; j++){
                System.out.print(ints[i][j]+" ");
            }
            System.out.println();
        }
    }

    private static void copyArr(int[][] ints, int[][] temp) {
        for(int i = 0 ; i < SIZE ; i++){
            for(int j = 0 ; j < SIZE ; j++){
                ints[i][j] = temp[i][j];
            }
        }
    }

    private static final int BLOCK = 0;
    private static final int EMPTY = 1;
    private static final int[] dz = {-1,1,0,0,0,0};
    private static final int[] dy = {0,0,-1,1,0,0};
    private static final int[] dx = {0,0,0,0,1,-1};

    public static int findRoute(int[][][] arr){
        if(arr[0][0][0] == BLOCK || arr[SIZE-1][SIZE-1][SIZE-1] == BLOCK){
            return INF;
        }
        Queue<int[]> q = new LinkedList<>();
        boolean[][][] visited = new boolean[SIZE][SIZE][SIZE];
        q.offer(new int[] {0,0,0});
        visited[0][0][0] = true;
        int time = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int s = 0 ; s < size ; s++){
                int[] now = q.poll();
                if(isGoal(now[0],now[1],now[2])){
                    return time;
                }
                for(int i = 0 ; i < 6; i++){
                    int nz = now[0] + dz[i];
                    int ny = now[1] + dy[i];
                    int nx = now[2] + dx[i];
                    if(checkBound(nz) && checkBound(ny)&&checkBound(nx) && !visited[nz][ny][nx] && arr[nz][ny][nx] == EMPTY){
                        visited[nz][ny][nx] = true;
                        q.offer(new int[] {nz,ny,nx});
                    }
                }
            }
            time++;
        }
        return INF;
    }
    public static int[][] rotationBoard(int[][] arr){
        int[][] temp = new int[SIZE][SIZE];
        for(int i = 0 ; i < SIZE ; i++){
            for(int j = 0 ; j < SIZE ; j++){
                temp[j][SIZE - 1- i] = arr[i][j];
            }
        }
        return temp;
    }

    public static boolean checkBound(int point){
        if(point >= 0 && point < SIZE){
            return true;
        }
        return false;
    }
    public static boolean isGoal(int z, int y, int x){
        if(z == y && y == x && x == SIZE-1){
            return true;
        }
        return false;
    }
}

16985번 Test코드

package BOJ;

import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import static org.junit.jupiter.api.Assertions.assertEquals;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class BOJ_16985Test {

    BOJ_16985 boj_16985;

    @BeforeEach
    void setUp() {
        boj_16985 = new BOJ_16985();
    }

    @Test
    void exampleTestFirst() {
        int[][][] arr = new int[][][]{
            {
                {1, 1, 1, 1, 1},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0}
            },
            {
                {1, 1, 1, 1, 1},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0}
            },
            {
                {1, 1, 1, 1, 1},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0}
            },
            {
                {1, 1, 1, 1, 1},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0}
            },
            {
                {1, 1, 1, 1, 1},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0}
            }
        };
        assertEquals(12,boj_16985.solution(arr));
    }
    @Test
    void exampleTest2() {
        int[][][] arr = new int[][][]{
            {
                {1, 1, 1, 1, 1},
                {1, 0, 0, 0, 1},
                {1, 0, 0, 0, 1},
                {1, 0, 0, 0, 1},
                {1, 1, 1, 1, 1}
            },
            {
                {0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0},
                {0, 1, 0, 1, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 0, 0}
            },
            {
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0}
            },
            {
                {0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0},
                {0, 1, 0, 1, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 0, 0}
            },
            {
                {1, 1, 1, 1, 1},
                {1, 0, 0, 0, 1},
                {1, 0, 0, 0, 1},
                {1, 0, 0, 0, 1},
                {1, 1, 1, 1, 1}
            }
        };
        assertEquals(-1,boj_16985.solution(arr));
    }

    @Test
    void exampleTest7() {
        int[][][] arr = new int[][][]{
            {
                {1, 1, 0, 0, 0},
                {0, 0, 0, 0, 1},
                {0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0}
            },
            {
                {0, 0, 1, 1, 1},
                {1, 0, 0, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 1, 1, 1},
                {0, 0, 1, 0, 0}
            },
            {
                {0, 0, 0, 0, 0},
                {0, 0, 1, 0, 1},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0},
                {0, 0, 1, 0, 1}
            },
            {
                {0, 0, 1, 0, 0},
                {1, 0, 0, 0, 0},
                {0, 0, 1, 1, 0},
                {1, 0, 1, 0, 0},
                {0, 0, 1, 0, 1}
            },
            {
                {0, 0, 1, 1, 0},
                {1, 1, 0, 1, 1},
                {0, 0, 0, 0, 1},
                {0, 1, 0, 1, 0},
                {0, 1, 0, 0, 0}
            }
        };
        assertEquals(16,boj_16985.solution(arr));
    }

    @Test
    void exampleTest5() {
        int[][][] arr = new int[][][]{
            {
                {0 ,0 ,0 ,1 ,0},
                {0 ,0 ,0 ,0 ,0},
                {1 ,0 ,1 ,1 ,1},
                {0 ,0 ,0 ,1 ,0},
                {0, 0 ,1 ,0 ,0}
            },
            {
                {0, 1, 0, 0, 0},
                {1, 1, 0, 0, 0},
                {1, 0, 0, 1, 0},
                {0, 1, 1, 1, 0},
                {0, 1, 0, 1, 0}
            },
            {
                {0, 0, 1, 0, 0},
                {1, 0, 0, 0, 0},
                {0, 1, 0, 0, 0},
                {0, 0, 1, 0, 0},
                {1, 1, 1, 0, 1}
            },
            {
                {1, 0, 0, 0, 1},
                {1, 0, 0, 0, 0},
                {0, 0, 1, 0, 1},
                {0, 1, 1, 0, 0},
                {0, 1, 0, 0, 0}
            },
            {
                {0, 0, 0, 1, 0},
                {1, 0, 0, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 1, 0, 0, 1},
                {0, 1, 0, 0, 0}
            }
        };
        assertEquals(22,boj_16985.solution(arr));
    }

    @Test
    void rotationBoard(){
        int[][] arr = new int[][]{
            {1,1,1,1,1},
            {0,0,0,0,0},
            {0,0,0,0,0},
            {0,0,0,0,0},
            {0,0,0,0,0}
        };
        int[][] rotatedArr = new int[][]{
            {0,0,0,0,1},
            {0,0,0,0,1},
            {0,0,0,0,1},
            {0,0,0,0,1},
            {0,0,0,0,1}
        };

        int[][] ints = boj_16985.rotationBoard(arr);

//        assertEquals(rotatedArr,ints);

        for(int i = 0 ; i < 5 ; i++){
            assertArrayEquals(rotatedArr[i],ints[i]);
        }
    }

    @Test
    void checkBoundSuccess(){
        assertEquals(true,boj_16985.checkBound(3));
    }
    @Test
    void checkBoundFail(){
        assertEquals(false,boj_16985.checkBound(5));
    }
    @Test
    void findRouteTest(){
        int[][][] arr = new int[][][]{
            {
                {1, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0}
            },
            {
                {1, 0, 0, 0, 0},
                {1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0}
            },
            {
                {0, 0, 0, 0, 0},
                {0, 1, 1, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0}
            },
            {
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 1, 1, 0},
                {0, 0, 0, 0, 0}
            },
            {
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0},
                {0, 0, 0, 1, 1}
            }
        };
        assertEquals(12,boj_16985.findRoute(arr));
    }
    @Test
    void findRouteTest2(){
        int[][][] arr = new int[5][5][5];
        for(int i = 0 ; i < 5 ; i++){
            for(int j = 0 ; j < 5 ; j++){
                for(int k = 0 ; k < 5; k++){
                    arr[i][j][k] = 1;
                }
            }
        }
        assertEquals(12,boj_16985.findRoute(arr));
    }
    @Test
    void isGoalTest(){
        assertEquals(true,boj_16985.isGoal(4,4,4));
    }
    @Test
    void isGoalTestFail(){
        assertEquals(false,boj_16985.isGoal(4,4,3));
        assertEquals(false,boj_16985.isGoal(4,3,4));
        assertEquals(false,boj_16985.isGoal(3,4,4));
    }
}

 

일단 입력이 3차원 배열로 들어오면서 입력을 만들기부터 힘들어졌습니다. 여기서부터 배보다 배꼽이 더 커지는 상황이 발생하였습니다. 또한, dfs에 대한 test코드를 작성하기 애매하여 작성하지 못하였습니다. Test코드에 집중해서 그런지, 결국 dfs에서 실수가 발생하여 문제를 찾는데 오래걸렸습니다. (depth를 i로 작성하는 실수..)

지금 구현보다 테스트 코드가 더 길며, 입력을 직접 작성할 때도 꽤 정신적으로 힘들었습니다. 약간 주객전도된 느낌이였습니다. 

장점도 존재하였습니다. 확실히 제가 작성한 코드에 대해 피드백이 빨라 제가 작성한 테스트 코드에 대해서는 자신감을 가질 수 있었고, 만약 틀린다면, 테스트 코드를 작성하지 않은 부분만 확인해 보면 되서 체크하는 코드의 양이 줄어드는 효과가 있었습니다. 

 

느낀점

알고리즘 문제풀이에서는 TDD를 사용하는 것은 권장드리지 않습니다. 개인적으로 SI회사에서 TDD를 잘 사용하지 않는 이유를 알게 되었던 것 같습니다. 

알고리즘 문제풀이에서 TDD를 사용해도 TDD의 장점을 온전히 활용하기 힘들 것 같습니다. 테스트에 통과할 만큼만 구현한다면 시간 초과를 피하기 어려울 것입니다. 그리고, 알고리즘 문제 풀이는 시간도 중요한데, 테스트 코드를 작성하므로써, 작성해야하는 코드양이 늘어 시간의 압박을 피하기 어렵습니다. 

장점도 존재하였습니다. TDD의 장점 중 하나인 피드백이 빠르다는 것입니다. 제가 코드를 작성하면 Test코드를 통해 바로 피드백이 되기 때문에 해당 코드에 대해서는 잘 동작한다는 자신감을 가질 수 있고, 틀려도 테스트 코드가 없는 부분들 위주로 찾아나가기 때문에 확인하는 코드의 범위를 줄일 수 있습니다.