꿀잠

https://leetcode.com/problems/n-queens/description/

체스판에 모든 퀸이 서로 공격할 수 없는 위치에 두는 방법을 묻는 문제이다.
퀸은 가로, 세로, 대각선으로 자유롭게 움직일 수 있으므로 해당 위치에 대한 방문 체크를 해주며 백트래킹을 하면 풀 수 있다. 가로, 세로, 대각선을 방문 체크하기 위해서 각 8방향의 배열을 만들어서 while문으로 해당 방향을 체크해주었다. 또한 row의 수는 n 이므로 row마다 퀸이 하나 씩 놓인다는 사실을 알 수 있다. 그러므로 0번 row에서 마지막 row까지 방문 체크를 하며 탐색 할 수 있다면 해당 문제의 조건에 부합하는 경우라는 것을 체크할 수 있다. 아래는 최종적으로 통과한 코드이다.

import java.util.*;  
  
public class Solution {  
  
    final String QUEEN = "Q";  
    final String EMPTY = ".";  
    int[] dr = {0, 1, 0, -1, 1, 1, -1, -1};  
    int[] dc = {1, 0, -1, 0, 1, -1, 1, -1};  
    boolean[][] visited;  
    List<List<String>> answer;  
    int n;  
  
    public List<List<String>> solveNQueens(int n) {  
        this.n = n;  
        answer = new ArrayList<>();  
        visited = new boolean[n][n];  
  
        for(int col = 0; col < n; col++){  
            visited[0][col] = true;  
            dfs(0, col);  
            visited[0][col] = false;  
        }  
  
        return answer;  
    }  
  
    private void dfs(int row, int col){  
        if(invalid(row, col)){  
            return;  
        }  
  
        int nextRow = row + 1;  
  
        if(nextRow == n){  
            List<String> result = new ArrayList<>();  
            StringBuilder resultRow = new StringBuilder();  
            for(int i = 0; i < n; i++){  
                for(int j = 0; j < visited.length; j++){  
                    String value = visited[i][j] ? QUEEN : EMPTY;  
                    resultRow.append(value);  
                }  
                result.add(resultRow.toString());  
                resultRow.setLength(0);  
            }  
  
            answer.add(result);  
            return;  
        }  
  
        for(int nextCol = 0; nextCol < n; nextCol++){  
            if(!visited[nextRow][nextCol]){  
                visited[nextRow][nextCol] = true;  
                dfs(nextRow, nextCol);  
                visited[nextRow][nextCol] = false;  
            }  
        }  
  
    }  
  
    private boolean invalid(int row, int col){  
  
        for(int i = 0; i < dr.length;i ++){  
            int nextRow = row + dr[i];  
            int nextCol = col + dc[i];  
            while(nextRow >= 0 && nextRow < n  
                    && nextCol >= 0 && nextCol < n){  
                if(visited[nextRow][nextCol]) return true;  
                nextRow = nextRow + dr[i];  
                nextCol = nextCol + dc[i];  
            }  
        }  
  
        return false;  
    }  
  
}

https://leetcode.com/problems/word-search/description/

주어진 보드의 문자를 연결해서 타겟으로 하는 문자열이 존재하는지 체크하는 문제이다.
기본적인 DFS 백트래킹으로 문제를 풀 수 있다. 보드의 상하좌우 탐색, 방문 체크, 조건 체크와 boolean 값 리턴 등에서 오류가 나지 않게 처리해주면 무난히 풀 수 있었다. 최종 코드는 아래와 같다.

public class Solution {  
  
    int[] dr = {1, 0, -1, 0};  
    int[] dc = {0, 1, 0, -1};  
    boolean[][] visited;  
  
    public boolean exist(char[][] board, String word) {  
        int m = board.length;  
        int n = board[0].length;  
        visited = new boolean[m][n];  
  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j < n; j++){  
                if(board[i][j] == word.charAt(0)){  
                    visited[i][j] = true;  
                    if(dfs(board, i, j, 0, word)){  
                        return true;  
                    };  
                    visited[i][j] = false;  
                }  
            }  
        }  
  
        return false;  
    }  
  
    private boolean dfs(char[][] board, int r, int c, int idx, String word){  
        if(idx == word.length() - 1){  
            return true;  
        }  
  
        if(idx > word.length() - 1){  
            return false;  
        }  
  
        int nextIdx = idx + 1;  
        for(int dir = 0; dir < 4; dir++){  
            int nextRow = r + dr[dir];  
            int nextCol = c + dc[dir];  
            if(nextRow >= 0 && nextRow < board.length  
                    && nextCol >= 0 && nextCol < board[0].length  
                    && !visited[nextRow][nextCol]  
                    && board[nextRow][nextCol] == word.charAt(nextIdx)  
            ){  
                visited[nextRow][nextCol] = true;  
                if(dfs(board, nextRow, nextCol, nextIdx, word)){  
                    return true;  
                };  
                visited[nextRow][nextCol] = false;  
            }  
        }  
  
        return false;  
    }  
}

같은 형태로 문자열 배열을 체크하는 문제가 있었는데 해당 문제는 상당히 어려웠었다. 이 문제를 해결한 이후 Trie 자료구조 알고리즘을 공부했다면 도전할 만 하다.

https://ygs3004.tistory.com/93

https://leetcode.com/problems/permutations/

주어진 배열의 순열을 모두 뽑아내는 문제이다. 가장 기본적인 형태의 알고리즘의 문제이다.
주어진 배열을 직접 스왑하면서 푸는 방식도 있지만 일반적인 백트래킹 방식으로도 해결할 수 있다.

백트래킹을 할 때는 항상 재귀 함수 이후 원 상태로 돌려주어야 한다는 점이다. 아래는 통과한 전체 코드이다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> permute(int[] nums) {  
        List<List<Integer>> answer = new ArrayList<>();  
        List<Integer> list = new ArrayList<>();  
        boolean[] visited = new boolean[nums.length];  
        dfs(nums, list, answer, visited);  
  
        return answer;  
    }  
  
    private void dfs(int[] nums, List<Integer> cur, List<List<Integer>> answer, boolean[] visited){  
        if(cur.size() == nums.length){  
            answer.add(new ArrayList<>(cur));  
            return;  
        }  
  
        for(int i = 0; i < nums.length; i++){  
            if(!visited[i]){  
                visited[i] = true;  
                cur.add(nums[i]);  
                int removeIdx = cur.size() - 1;  
                dfs(nums, cur, answer, visited);  
                cur.remove(removeIdx);  
                visited[i] = false;  
            }  
        }  
    }  
}

https://leetcode.com/problems/combination-sum/description/

타겟의 합계를 맞추기 위해 알맞은 요소의 조합을 찾는 문제이다.
전형적인 DFS 백트래킹 문제로 조건들을 문제에 맞춰 해결 해주면 된다. 크게 특이사항은 없는 문제였다.

class Solution {  
  
    static int[] candidates;  
    static int target;  
    static List<List<Integer>> answer;  
  
    public List<List<Integer>> combinationSum(int[] candidates, int target) {  
        this.candidates = candidates;  
        this.target = target;  
        this.answer = new ArrayList<>();  
        List<Integer> init = new ArrayList<Integer>();  
        for(int i = 0; i < candidates.length; i++){  
            init.add(candidates[i]);  
            dfs(0, i, init);  
            init.remove(0);  
        }  
  
        return answer;  
    }  
  
    private void dfs(int sum, int idx, List<Integer> list){  
        int curCandidate = candidates[idx];  
        sum += curCandidate;  
        if(sum == target){  
            answer.add(new ArrayList<>(list));  
            return;  
        }  
  
        // 중복 조합을 피하기위해 현재 idx보다 높은 경우만 체크  
        for(int i = idx; i < candidates.length; i++){  
            int nextCandidate = candidates[i];  
            if(nextCandidate + sum > target) continue;  
  
            list.add(nextCandidate);  
            int curListIdx = list.size() - 1;  
            dfs(sum, i, list);  
            list.remove(curListIdx);  
        }  
    }  
}

https://leetcode.com/problems/subsets/description/

주어진 배열의 모든 subset을 List로 리턴하는 문제이다.
각 요소를 순회하기 위하여 dfs로 백트래킹을 하여 가능하며, 중복 요소를 제거하기 위하여
현재 인덱스 이후 기준으로 dfs 탐색 하였다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> subsets(int[] nums) {  
        List<List<Integer>> answer = new ArrayList<>();  
        List<Integer> cur = new ArrayList<>();  
        boolean[] visited = new boolean[nums.length];  
        dfs(answer, cur, -1, visited, nums);  
  
        return answer;  
    }  
  
    private void dfs(List<List<Integer>> answer, List<Integer> cur, int curidx, boolean[] visited, int[] nums){  
        // Array 의 값을 복사하여 넣어준다.  
        List<Integer> subset = new ArrayList<>(cur);  
        answer.add(subset);  
  
        for(int i = curidx + 1; i < visited.length; i++){  
            if(!visited[i]){  
                cur.add(nums[i]);  
                int curSize = cur.size();  
                visited[i] = true;  
                dfs(answer, cur, i, visited, nums);  
                // 값을 다시 초기화하여 백트래킹 한다.  
                visited[i] = false;  
                cur.remove(curSize - 1);  
            }  
        }  
    }  
}

서브 셋을 추가할 땐 해당 배열을 복사해서 추가해주었다.

List의 참조 값을 바라보므로 해당 시점의 배열 요소로 복사해서 넣어주어야 한다.

코딩테스트 문제를 풀 다 시간 초과를 해결했던 경험에 대한 기록이다.

백준의 텀프로젝트 문제를 풀던 중(https://www.acmicpc.net/problem/9466)
내가 작성한 코드가 충분히 최적화 되었다고 생각했음에도 계속 시간 초과가 발생하였다.
관련하여 문제를 찾던 중 자바의 배열 생성이 시간 초과의 원인이 될 수 있다는 글을 발견하고, 해당 부분을 수정하여 통과하였다.

    private static int solution() throws IOException {
        int studentNum = Integer.parseInt(br.readLine());
        int[] team = new int[studentNum + 1];
        String[] input = br.readLine().split(" ");
        for(int i = 1; i <= studentNum; i++){
            team[i] = Integer.parseInt(input[i-1]);
        }

        checked = new boolean[studentNum + 1];
        result = studentNum;

        for(int i = 1; i <= studentNum; i++){
            if(checked[i]) continue;
            // 배열 초기화
            visited = new int[studentNum + 1];
            findTeam(team, i, 1, visited);
        }

        return result;
    }

    private static void findTeam(int[] team, int student, int seq, int[] visited){
        if(checked[student]) return;
        checked[student] = true;
        visited[student] = seq;

        int next = team[student];
        if(visited[next] != 0){
            result -= (seq - visited[next] + 1);
        }else{
            findTeam(team, next, seq + 1, visited);
        }
    }

시간 초과가 나던 시점의 내 코드는 위와 같았으며, 완전 탐색을 위하여 탐색 방문 배열을 new 명령어로 생성하고 있었다. 해당 배열의 크기는 최대 100001의 크기를 갖는 문제이다.

    private static int solution() throws IOException {
        int studentNum = Integer.parseInt(br.readLine());
        int[] team = new int[studentNum + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= studentNum; i++){
            team[i] = Integer.parseInt(st.nextToken());
        }

        checked = new boolean[studentNum + 1];
        int[] visited = new int[studentNum + 1];
        result = studentNum;
        for(int i = 1; i <= studentNum; i++){
            if(checked[i]) continue;
            findTeam(team, i, 0, visited);
        }

        return result;
    }

    private static void findTeam(int[] team, int student, int seq, int[] visited){
        if(checked[student]) return;
        seq++;
        checked[student] = true;
        visited[student] = seq;

        int next = team[student];
        if(visited[next] != 0){
            result -= (seq - visited[next] + 1);
        }else{
            findTeam(team, next, seq, visited);
        }

        // dfs 내부에서 사용후 값 원상복구
        visited[student] = 0;
    }

}

시간 초과를 해결한 코드는 위와 같다. dfs를 반복하기 이전에 생성한 배열의 값을 new 가 아닌 직접 초기화 하여 배열을 사용하였다. 참고한 글(https://okky.kr/questions/1450047)에 따르면 배열을 생성한다는 것은 새로운 객체의 메모리에 할당 받는 부분, java의 경우 해당 배열의 초기 값을 초기화하는 부분 등으로 인하여 런타임 실행 시간이 늘어날 수 있다고 한다. 단순한 코드의 차이였지만 객체 생성의 효율에 대해 고민할 수 있었다.