방어적 복사(defensive copying) : 가변 객체를 다룰 때, 해당 객체를 외부로부터 보호하기 위해 사용되는 기법이다. 이 기법은 객체의 내부 상태를 변경할 수 없도록 하기 위해 객체를 복사하여 사용하는 것을 의미한다.
악의적인 의도를 가진 사람들이 시스템의 보안을 뚫으려는 시도가 늘고있는만큼, 클라이언트가 내가 작성한 코드의 불변식을 깨뜨리려 혈안이 되어 있다고 가정하고 방어적으로 프로그래밍해야한다.
생성자에서 받은 가변 매개변수 각각을 방어적 복사하고, 이 복사본으로 유효성을 검사해야한다. 그리고 인스턴스 안에서는 원본이 아닌 복사본을 사용한다. 그리고 이때 매개변수가 제3자에 의해 확장할 수 있는 타입이라면 방어적 복사본을 만들 때 clone을 사용해서는 안 된다.
clone() 메서드는 객체의 얕은 복사(shallow copy)를 생성하므로, 내부에 포함된 가변 객체들은 동일한 참조를 유지하게 됩니다. 이는 복사본을 사용하여도 원본 객체의 상태 변경이 복사본에 영향을 미칠 수 있음을 의미합니다.
핵심 정리 : 클래스가 클라이언트로부터 받는 혹은 클라이언트로 반환하는 구성요소가 가변이라면 그 요소는 반드시 방어적으로 복사해야 한다. 복사 비용이 너무 크거나 클라이언트가 그 요소를 잘못 수정할 일이 없음을 신뢰한다면 방어적 복사를 수행하는 대신 해당 구성요소를 수정했을 때의 책임이 클라이언트에 있음을 문서에 명시하도록 하자.
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];
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;
}
핵심 정리 : 메서드나 생성자를 작성할 때면 그 매개변수들에 어떤 제약이 있을지 생각해야 한다. 그 제약들을 문서화하고 메서드 코드 시작 부분에서 명시적으로 검사해야 한다. 이런 습관을 반드시 기르도록 하자. 그 노력은 유효성 검사가 실제 오류를 처음 걸러낼 때 충분히 보상받을 것이다.
import java.io.*;
import java.util.*;
public class Main {
static int N, answer = Integer.MAX_VALUE;
static int[][] map;
static boolean[] visited;
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());
map = new int[N][N];
visited = new boolean[N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < N; i++) {
visited[i] = true;
backTracking(i, i, 0, 0);
}
System.out.println(answer);
}
/**
* @param start : 메서드 실행 전 위에서 정해줌
* @param now : 현재 내가 위치한 도시
* @param sum : 현재위치한 도시까지 사용한 비용
* @param depth
*/
static void backTracking(int start, int now, int sum, int depth) {
if (depth == N - 1) { // 모든 도시를 모두 방문한 경우, N-1인 이유는 백트래킹 메서드를 실행하기 전에 이미 방문함
if (map[now][start] != 0) { // 마지막 도시에서 처음 도시로 가는 비용 더하기
sum += map[now][start];
answer = Math.min(answer, sum); // 최종적으로 나온 비용
}
return;
}
for (int i = 0; i < N; i++) {
if (!visited[i]) { // 방문하지 않은 도시일경우
if (map[now][i] != 0) { // 갈수 있는 도시일경우
visited[i] = true; // 방문했다면 true
backTracking(start, i, sum + map[now][i], depth + 1);
visited[i] = false; // 방문이 끝나면 false
}
}
}
}
}
[풀이]
시작하는 도시가 1번도시로 고정이 아닌 어느도시에서 시작하든 최소비용을 찾는것이기 때문에 N번 반복한다.
for (int i = 0; i < N; i++) {
visited[i] = true;
backTracking(i, i, 0, 0);
}
백트래킹 메서드의 매개변수 start 는 순회를 시작한 도시의 위치로 메서드를 실행할 때 정해진다.
매개변수 now는 현재 내가 위치한 도시의 위치를 뜻한다.
매개변수 sum은 현재 내가 now에 올때까지 사용한 비용을 뜻한다.
매개변수 depth는 모든도시를 순회했는지 체크한다.
for문을 돌며 방문하지 않은 도시이며 map[i][j]가 0이 아닌도시(방문할 수 있는 도시) 라면 백트래킹을 재귀적으로 수행한다.
이때 넣어주어야 하는 매개변수들은 순회를 시작한 도시 start, 다음 방문할 도시 i, 현재까지 사용한 비용(sum) + 현재 위치에서 i까지 가는 비용(map[now][i]), depth + 1이다.
for (int i = 0; i < N; i++) {
if (!visited[i]) { // 방문하지 않은 도시일경우
if (map[now][i] != 0) { // 갈수 있는 도시일경우
visited[i] = true; // 방문했다면 true
backTracking(start, i, sum + map[now][i], depth + 1);
visited[i] = false; // 방문이 끝나면 false
}
}
}
depth 가 N-1이 되면 모든도시를 방문한 것이다. depth가 N이아닌 N-1인 이유는 순회를 시작한 도시는 메서드 실행전 체크하기 때문이다.
depth가 N-1이 되었다면 마지막 도착한 도시에서 순회를 시작한 도시로 돌아와야하기 때문에 map[now][start] != 0 이라면
sum += map[now][start]를 해주어 마지막 비용을 추가해준다.
if (depth == N - 1) { // 모든 도시를 모두 방문한 경우, N-1인 이유는 백트래킹 메서드를 실행하기 전에 이미 방문함
if (map[now][start] != 0) { // 마지막 도시에서 처음 도시로 가는 비용 더하기
sum += map[now][start];
answer = Math.min(answer, sum); // 최종적으로 나온 비용
}
return;
}
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static boolean[] checked;
static int[] arr, tmp;
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
checked = new boolean[N];
arr = new int[N];
tmp = new int[N];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr); // 오름차순 정렬
backTracking(0, 0);
bw.flush();
}
static void backTracking(int depth, int start) throws Exception {
if (depth == M) { // depth 가 M이 될때까지 실행
for (int i = 0; i < M; i++) {
bw.write(tmp[i] + " ");
}
bw.write("\n");
return;
}
for (int i = start; i < N; i++) {
tmp[depth] = arr[i];
backTracking(depth + 1, i);
}
}
}
[풀이]
사용한 숫자를 중복해서 사용하기 위해 boolean 배열을 사용하지 않는다.
비내림차순을 만족하기위해 매개변수를 depth 이외에 하나를 추가해준다. 매개변수는 i로 준다.
