N-Queen, 어디까지 했나?

 

어제와 오늘 코딩 도장 문제로 N-Queen 문제가 주어졌다. 결론부터 말하자면 어제 Java, 오늘 JavaScript 둘 다 못 풀었는데, 끊기 전에 아쉬움이라도 털어보는 마음으로 1시간 동안 문제를 어떻게 해결하려 했었는지 기록해본다.

 

문제를 일단 적어보았다. 예를 들어서 n이 4가 주어졌다고 하면 체스판의 크기는 4*4, 놓아야 하는 퀸의 수는 4개일 것이었다.

 

어디서부터 퀸을 놓아야 할지 모르겠으니 우선 0행 0열의 자리에 놓아보았다.

 

 

퀸	X	X	X
X	X
X		X
X			X

 

 

적어보고 나니 퀸을 놓을 수 없는 자리와 놓을 수 있는 자리가 구분되어 보였고, 그 다음 자리에도 한번 놓아보았다.

 

 

퀸	X	X	X
X	X	퀸	X
X	X	X	X
X		X	X

 

 

이렇게 하니 자리가 하나밖에 남지 않는 것이 눈에 들어왔다. 일단 문제 조건 상 이렇게 되면 실패다. 오... 그럼 두 번째 퀸은 저 자리에 들어가서는 안 될 것 같고, 남은 자리에도 한 번씩 계속 퀸을 넣어봐야 하겠구나 생각이 들었다.

 

일단 풀이 방법론에 대해 생각해보는 범위는 여기까지 진행했고, 이 시점까지 생각한 과정을 진행할 수 있도록 하는 구현을 해보려 했다. 처음으로 만드는 것을 시도한 메서드는 퀸을 체스판에 놓는 것이었다. 메서드에 체스판과 놓아야 하는 퀸의 개수가 주어지면, 메서드의 로직을 거쳐 퀸이 놓여지고 X 표시가 찍힌 체스판과, 놓아야 하는 퀸의 개수에서 1을 빼서 반환하도록 하는 메서드를 만들 계획이었다.

 

@Test
  void putQueenCase1() {
    NQueen test = new NQueen();

    int n = 4;
    char[][] board = {
        {'O', 'O', 'O', 'O'},
        {'O', 'O', 'O', 'O'},
        {'O', 'O', 'O', 'O'},
        {'O', 'O', 'O', 'O'}
    };
    int[] position = new int[]{0, 0};

    board = test.putQueen(board, position);

    assertThat(board).isDeepEqualTo(new char[][]{
        {'Q', 'X', 'X', 'X'},
        {'X', 'X', 'O', 'O'},
        {'X', 'O', 'X', 'O'},
        {'X', 'O', 'O', 'X'}
    });
  }

 

이런 식의 테스트를 일단 작성했다. 해당 테스트를 통과하게 하는 소스코드를 작성하는 데 20분 가량의 시간을 썼고, 아쉽게도 뒷 내용은 코딩 도장 풀이 시간 안에 생각해내지 못하면서 코딩 도장 시간을 마쳤다. 글을 쓰는 지금 작동되지 않던 이유가 눈에 들어와 조금 보완해서 해당 테스트는 통과하는 소스코드를 작성했다. 어제는 for 반복문의 조건 검사를 지금 작성한 코드와는 거꾸로 하고 있었다. 사소한 부분을 자꾸자꾸 놓치면서 시간을 잡아먹는 부분이 아쉽다.

 

public char[][] putQueen(char[][] board, int[] position) {
    int positionX = position[0];
    int positionY = position[1];

    board[positionY][positionX] = 'Q';

    for (int x = positionX + 1; x < board[positionY].length; x += 1) {
      board[positionY][x] = 'X';
    }

    for (int y = positionY + 1; y < board.length; y += 1) {
      board[y][positionX] = 'X';
      board[y][y] = 'X';
    }

    return board;
  }

 

 

오늘은 그냥 포기할 심산으로 해당 문제를 검색해봤는데, 내가 생각했던 풀이 방법론이 '백트래킹'이라는 방법론이라는 사실을 알 수 있었다. 가능한 모든 경우의 수를 마치 미로의 모든 경로를 다 따져보듯 탐색해나가는데, 만약 특정 시점에서 이쪽으로는 더 탐색해도 해답이 나올 가능성이 없음을 알게 될 경우에는 그 이전으로 돌아가서 남은 경우의 수들을 다시 하나씩 탐색하는 식의 기법이라고 하는 것 같다.

 

일단 아쉬운 방법으로 정답은 작성해서 제출은 해 놓으려고 하지만, 따로 표시를 해 놓는다면 나중의 내가 표시를 보고 다시 한 번 문제를 직접 풀어보는 것을 도전해보지 않겠나 싶은 생각으로 아쉬움을 달래본다.