<stdio.han>

방어적 복사(defensive copying) : 가변 객체를 다룰 때, 해당 객체를 외부로부터 보호하기 위해 사용되는 기법이다. 이 기법은 객체의 내부 상태를 변경할 수 없도록 하기 위해 객체를 복사하여 사용하는 것을 의미한다.

악의적인 의도를 가진 사람들이 시스템의 보안을 뚫으려는 시도가 늘고있는만큼, 클라이언트가 내가 작성한 코드의 불변식을 깨뜨리려 혈안이 되어 있다고 가정하고 방어적으로 프로그래밍해야한다.

생성자에서 받은 가변 매개변수 각각을 방어적 복사하고, 이 복사본으로 유효성을 검사해야한다. 그리고 인스턴스 안에서는 원본이 아닌 복사본을 사용한다. 그리고 이때 매개변수가 제3자에 의해 확장할 수 있는 타입이라면 방어적 복사본을 만들 때  clone을 사용해서는 안 된다.

• clone() 메서드는 객체의 얕은 복사(shallow copy)를 생성하므로, 내부에 포함된 가변 객체들은 동일한 참조를 유지하게 됩니다. 이는 복사본을 사용하여도 원본 객체의 상태 변경이 복사본에 영향을 미칠 수 있음을 의미합니다.

핵심 정리 : 클래스가 클라이언트로부터 받는 혹은 클라이언트로 반환하는 구성요소가 가변이라면 그 요소는 반드시 방어적으로 복사해야 한다. 복사 비용이 너무 크거나 클라이언트가 그 요소를 잘못 수정할 일이 없음을 신뢰한다면 방어적 복사를 수행하는 대신 해당 구성요소를 수정했을 때의 책임이 클라이언트에 있음을 문서에 명시하도록 하자.

https://school.programmers.co.kr/learn/courses/30/lessons/169199

[난이도]

- level 2

[알고리즘]

- BFS

[코드]

import java.util.*;
import java.io.*;

class Solution {
    public int solution(String[] board) {
        int answer = 0;
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        boolean[][] visited = new boolean[board.length][board[0].length()];
        Queue<int[]> queue = new LinkedList<>();
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length();j++){
                if(board[i].charAt(j) == 'R')
                { // 시작위치 저장
                    queue.offer(new int[]{i, j, 0});
                    visited[i][j] = true;
                }   
            }
        }
        
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            if(board[x].charAt(y) == 'G'){
                answer = count;
                return answer;
            }
            for(int i=0;i<4;i++){
                int nx = x;
                int ny = y;
                while(nx>=0&&nx<board.length&&ny>=0&&ny<board[0].length()&&board[nx].charAt(ny) != 'D'){ // 범위내에 있거나, 장애물 'D' 를 만날때 까지 계속 이동
                    nx += dx[i];
                    ny += dy[i];
                }
                // 범위 벗어나거나 장애물 만나기 직전으로 수정
                nx -= dx[i];
                ny -= dy[i];
                
                if(visited[nx][ny] || (x == nx && y == ny)){ // 방문한 적이 없고 같은 위치가 아닐경우
                    continue;
                    
                }
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx, ny, count+1});
                }
            }
        answer = -1;
        return answer;
    }
}

[풀이]

일반적인 bfs, 4방탐색 알고리즘을 활용한 문제이다.

다른점이 있다면 4방탐색 시 한 칸만 움직이는게 아닌 장애물을 만나거나 범위를 벗어나기전까지 계속 움직여야 한다는점이다.

                while(nx>=0&&nx<board.length&&ny>=0&&ny<board[0].length()&&board[nx].charAt(ny) != 'D'){ // 범위내에 있거나, 장애물 'D' 를 만날때 까지 계속 이동
                    nx += dx[i];
                    ny += dy[i];
                }
                // 범위 벗어나거나 장애물 만나기 직전으로 수정
                nx -= dx[i];
                ny -= dy[i];

https://www.acmicpc.net/problem/14889

[난이도]

- Silver 1

[알고리즘]

- DFS

- 완전탐색

- 백트래킹

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int N, answer = Integer.MAX_VALUE;
    static int[][] players;
    static boolean[] selected;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        players = new int[N][N];
        selected = new boolean[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                players[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solve(0, 0);
        System.out.println(answer);
        br.close();

    }
    static void solve(int depth, int index) {
        if (depth == N/2) {
            int startTeam = 0;
            int linkTeam = 0;

            for (int i = 0; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    if (selected[i] && selected[j]) {
                        startTeam += players[i][j];
                        startTeam += players[j][i];
                    } else if (!selected[i] && !selected[j]) {
                        linkTeam += players[i][j];
                        linkTeam += players[j][i];
                    }
                }
            }

            int diff = Math.abs(startTeam - linkTeam);
            answer = Math.min(answer, diff);
            return;
        }
        for (int i = index; i < N; i++) {
            if (!selected[i]) {
                selected[i] = true;
                solve(depth + 1, i + 1);
                selected[i] = false;
            }
        }
    }
}

[풀이]

boolean 배열로 선택한 선수와 선택하지 않은선수를 나눠계산한다.

            for (int i = 0; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    if (selected[i] && selected[j]) {
                        startTeam += players[i][j];
                        startTeam += players[j][i];
                    } else if (!selected[i] && !selected[j]) {
                        linkTeam += players[i][j];
                        linkTeam += players[j][i];
                    }
                }
            }

solve의 매개변수로 depth와 index를 주었다.

        for (int i = index; i < N; i++) {
            if (!selected[i]) {
                selected[i] = true;
                solve(depth + 1, i + 1);
                selected[i] = false;
            }
        }

for문을 돌며 선수를 선택할 때 i를 index로주고 선수를 선택했다면 매개변수를 건네줄때 i + 1로 주어 중복탐색을 줄여 시간초과를 방지할 수 있다.

https://www.acmicpc.net/problem/2961

[난이도]

- Silver 2

[알고리즘]

- 완전탐색

- DFS

- 백트래킹

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int N, answer = Integer.MAX_VALUE;
    static int[][] ingredient;
    static boolean[] selected;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        ingredient = new int[N][2];
        selected = new boolean[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            ingredient[i][0] = Integer.parseInt(st.nextToken());
            ingredient[i][1] = Integer.parseInt(st.nextToken());
        }
        solve(0, 1, 0, 0);
        System.out.println(answer);
    }

    // 트리의 깊이, 신맛, 쓴맛, 선택한 음식 개수
    static void solve(int depth, int sour, int bitter, int selectedCount) {
        if (depth == N) {
            if (selectedCount != 0) { // 1개 이상의 재료를 선택
                if (Math.abs(sour - bitter) < answer) { // 최솟값으로 갱신
                    answer = Math.abs(sour - bitter);
                }
            }
            return;
        }

        // 완전탐색을 위해 선택한경우와 선택하지 않은 경우를 나누어 진행
        solve(depth + 1, sour * ingredient[depth][0], bitter + ingredient[depth][1], selectedCount + 1); // 선택
        solve(depth + 1, sour, bitter, selectedCount); // 비선택
    }
}

[풀이]

부분집합을 구하는 방식을 활용해 완전탐색을 해야한다.

1. 재료를 선택한 경우와 선택하지 않은 경우 모두를 고려해서 재귀함수를 진행한다.

2. 트리의 깊이가 N이 될때까지 반복한다.

3. 트리의 깊이가 N이면서 1개 이상의 재료를 선택했으며 현재 알고있는 최소값보다 새로구한 값이 더 작을 때 answer를 갱신해준다.

매개변수 유효성 검사는 메서드나 함수가 실행되기 전에 입력 값이 기대한 조건을 충족하는지 확인하는 과정이다. 이를 통해 잘못된 입력이 메서드나 함수에 전달되는 것을 방지할 수 있다.

아래 코드처럼 문서화하고 명시적으로 검사할 수 있다.

/**
 * 두 개의 양수를 더하는 메서드
 * @param a 첫 번째 양수
 * @param b 두 번째 양수
 * @return 두 양수의 합
 * @throws IllegalArgumentException 매개변수가 음수인 경우 발생
 */
public int add(int a, int b) {
    if (a < 0 || b < 0) {
        throw new IllegalArgumentException("매개변수는 양수이어야 합니다.");
    }
    return a + b;
}

핵심 정리 : 메서드나 생성자를 작성할 때면 그 매개변수들에 어떤 제약이 있을지 생각해야 한다. 그 제약들을 문서화하고 메서드 코드 시작 부분에서 명시적으로 검사해야 한다. 이런 습관을 반드시 기르도록 하자. 그 노력은 유효성 검사가 실제 오류를 처음 걸러낼 때 충분히 보상받을 것이다.