상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리

며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면,

2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다.

(1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

import java.util.Scanner;

/*
 * 재귀메서드를 활용하여 1번째 날부터 N번째 날까지 모든 경우의 수를 탐색.
 */
public class Main {
	static int N, max;
	static int[][] schedule;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		max = 0;
		N = sc.nextInt();
		schedule = new int[N][2];

		for (int i = 0; i < N; i++) {
			schedule[i][0] = sc.nextInt();
			schedule[i][1] = sc.nextInt();
		}

		DFS(0, 0);

		System.out.println(max);
	}

	private static void DFS(int idx, int profit) {
		if (idx >= N) {
			max = Math.max(profit, max);
			return;
		}

		// 해당 날짜의 상담을 기간 내에 마칠 수 있는지 확인
		if (schedule[idx][0] <= N - idx) {
			// 상담을 한다
			DFS(idx + schedule[idx][0], profit + schedule[idx][1]);
		}
		DFS(idx + 1, profit);
	}
}

개선 사항

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

public class Main {
    static StringTokenizer st; 
    static int[] dp; 

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // N: 상담 가능한 총 날짜 수

        dp = new int[N + 1]; // dp 배열 초기화 (0 ~ N까지)

        for (int i = 0; i < N; i++) { // i: 현재 날짜
            st = new StringTokenizer(br.readLine()); // i번째 상담의 기간(t)과 수익(p)을 입력
            int t = Integer.parseInt(st.nextToken()); // 상담 기간
            int p = Integer.parseInt(st.nextToken()); // 상담 수익

            if (i + t <= N) { // 상담이 기한 내에 종료되는 경우
                dp[i + t] = Math.max(dp[i + t], dp[i] + p); // i + t일의 최대 수익 갱신
            }
            dp[i + 1] = Math.max(dp[i], dp[i + 1]); // 다음 날로 넘어갈 때 최대 수익 유지
        }

        System.out.println(dp[N]); // N일에 가능한 최대 수익 출력
    }
}

동적프로그래밍 알고리즘을 이용해 풀 수 있다.

이전 배열을 참고해 중복 계산을 피하면서도 최적의 값을 구할 수있다.

처음 풀 때도 dp방식을 생각하지 않은 것은 아닌데,

마땅한 풀이가 생각나지 않아 브루트포스로 문제를 해결했다.

더 많은 동적프로그래밍 문제를 풀어봐야겠다.

Template Syntax

• 보간법 : 
  머스태쉬 구문(중괄호 2개를 겹쳐 씀)안에 데이터를 텍스트 형태로 렌더링함

<span>{{ message }}</span>	//message 안에 데이터를 동적으로 할당

• 바인딩 :
  v-bind 디렉티브를 사용해 HTML 태그에 적는 속성들을 동적으로 바인딩할 수 있다.

<div v-bind:id="dynamicId"></div>	// dynamicId로 선언해 둔 값이 id 값으로 저장됨

Dynamic Data Binding

데이터를 동적으로 바꿔가며 HTML 속성을 조작하거나 활용할 수 있다.

• 단방향 바인딩 : 동적인 데이터를 화면 상에 반영되도록 하는 바인딩.
  
  
  
• 양방향 바인딩 : 동적인 데이터를 화면 상에 반영되도록 하고, 화면 상에 입력된 값이 데이터를 바꿀 수도 있음.
  
  

<input v-model="message" />

Event Handling

v-on 디렉티브를 사용하여 DOM 이벤트를 듣고, 그에 대한 반응으로 메소드를 실행하는 기능

// 이벤트 리스너 추가
<button v-on:click="handleClick">Click me</button>


//////////////////////////////////////////////////
// 자바스크립트 파트에서 메소드 정의
methods: {
  handleClick() {
    alert('Button clicked!');
  }
}

Event Handling

폼 입력 바인딩은 v-model을 사용하여 입력 폼 요소와 애플리케이션 데이터 사이의 양방향 바인딩을 생성

// 텍스트 입력
<input v-model="username" placeholder="Enter your name">

// 체크박스
<input type="checkbox" v-model="checked">


// 라디오 버튼
<input type="radio" v-model="picked" value="One">
<input type="radio" v-model="picked" value="Two">


// 셀렉트 박스
<select v-model="selected">
  <option disabled value="">Please select one</option>
  <option>A</option>
  <option>B</option>
</select>



<script src="https://cdn.jsdelivr.net/npm/vue@3.2.37/dist/vue.global.prod.min.js"></script>
    <script>
      // Vue 애플리케이션을 생성하고 관리합니다.
      const { createApp, ref } = Vue;

      const app = createApp({
        setup() {
        	const username = ref('');	// 텍스트 입력 값이 여기에 들어감
            const checked = ref(false);	// 체크박스 true/false 값이 여기에 들어감
			const picked = ref('');		// 라디오버튼 선택 값이 여기에 들어감
            const selected = ref('');	// 셀렉트박스 선택 값이 여기에 들어감

          // setup 함수에서 반환하는 객체는 템플릿에서 사용됩니다.
          return { username, checked, picked, selected };
        },
      });

      // Vue 인스턴스를 #app 요소에 마운트합니다.
      app.mount('#app');
    </script>
</body>
</html>

Vue.js 란?

• JavaScript의 프레임워크 중 하나.  (react.js, angular 등 다른 프레임워크들도 있음)
  
• 다른 프레임워크에 비해 직관적이기 때문에 배우기가 더 용이함
  
  
• 템플릿 기반의 구문을 사용해 HTML과 JavaScript를 명확히 분리 가능 (가독성 좋음)

CSR(Client-Side Rendering)과 SSR(Server-Side Rendering)

1. CSR :
   
   장점
   
   -  초기 로딩 후에는 모든 렌더링이 클라이언트 측에서 처리됨 -> 빠르게 느껴짐
   
   -  서버 부하가 감소, 서버는 단지 데이터(JSON)만 전송하면 됨
   
   
   단점
   
   - 애플리케이션의 자바스크립트 전체를 다운로드해야하므로 초기 속도는 느릴 수 있음
   
   -  검색 엔진이 제대로 반영되지 못할 수 있음
   
   
   
2. SSR :
   
   
   장점
   
   -  서버에서 HTML을 완성해 보내기 때문에, 검색엔진 최적화에는 더 적절
   
   - 첫 페이지에서 모든 정보를 다운로드할 필요가 없으므로 첫 페이지 로딩은 더 빠
   
   
   단점
   
   - 모든 요청이 서버에서 렌더링되므로 부하가 증가
   
   - 클라이언트와 서버 간 상태를 동기화하는 것이 복잡할 수 있음.

기본 구조

<!DOCTYPE html>
<html lang="ko">
  <head>
    <meta charset="UTF-8" />
    <title>FirstVueApp</title>
    ///////////////////////////////////////
    // Vue를 사용하기 위해 필수. CDN방식 
    <script src="https://unpkg.com/vue@3/dist/vue.global.js"></script>
  </head>

  <body>
    <div id="app">
      <h1>{{ message }}</h1>
      <button v-on:click="count++">Count is: {{ count }}</button>
    </div>
    
    ///////////////////////////////////////////
    <script>
    
      // Vue 객체에서 createApp과 ref를 구조분해 할당으로 생성
      const { createApp, ref } = Vue;

	  // createApp 함수 호출하여 Vue 앰 인스턴스를 생성
      const app = createApp({	
        setup() {	// <- Composition API에서 컴포넌트의 반응형 상태와 함수를 정의
        
          // ref로 반응형 데이터 생성
          const message = ref("Hello vue");
          const count = ref(0);
		
          // setup함수에서 반환하는 객체들. 템플릿에서 사용하려면 반드시 반환해주어야 함
          return {
            message,
            count,
          };
        },
      });

      app.mount("#app");
    </script>
    /////////////////////////////////////////////
  </body>
</html>

createApp 함수를 사용해 앱 객체를 생성하고, 반응형 데이터 생성을 위해 ref객체를 생성한다.

const {createApp, ref} = Vue   -> 구조분해할당으로 객체 생성

템플릿 영역에서의 unwrap

Vue에서는 동적으로 화면을 바꾸고, 렌더링하기 위해

ref() 를 사용해 반응형 데이터를 생성한다.

즉 ref() 객체 안에 값을 집어 넣는 것.

이를 자바스크립트 안에서 값을 참조하기 위해선

.value를 사용해 값을 참조할 수 있고,

템플릿(HTML) 영역에서는 알아서 unwrap해주기 때문에 .value를 사용할 필요가 없다!!

<!DOCTYPE html>
<html lang="ko">

<head>
  <meta charset="UTF-8" />
  <title>FirstVueApp</title>
  ///////////////////////////////////////
  // Vue를 사용하기 위해 필수. CDN방식
  <script src="https://unpkg.com/vue@3/dist/vue.global.js"></script>
</head>

<body>
  <div id="app">
    <h1>{{ message }}</h1>
    <button v-on:click="count++">Count is: {{ count }}</button>
  </div>

  <script>
    const App = {
      setup() {
        const count = ref(0);

        function increment() {
          count.value++;
        }

        return { count, increment }
      }
    };

    const app = createApp(App);
    app.mount('#app');
  </script>
</body>

AJAX란?

• Asynchronous JavaScrpt and XML
  
  
• 비동기적인 방식으로 서버와 통신
  
  
• 새로고침을 하지 않아도 서버와 통신해 웹페이지를 갱신할 수 있다.
  
  
• 한번에 서버의 데이터를 모두 받아오기 때문에 처음엔 느리지만, 이후로는 빠르게 처리할 수 있음
  
  
• 서버 입장에서는 부하가 감소하는 효과
  
  
• 클라이언트 입장에서는 더 빠르게 느낌

AJAX의 동작 방식: 동기 vs 비동기

1. 동기 :
   
   - 요청을 보낸 이후 서버로부터 응답을 받아야 다음 작업을 진행.
   
   - 코드가 단순하고 직관적이기에 개발자 입장에서는 더 용이할 수 있음
   
   - 하지만 한 가지 요청이 막히면, 다음 요청까지 막혀 멈춰버리는 현상 발생
   
   
   
   
   
2. 비동기 :
   
   - 페이지를 처음 불러들일 때, 대부분의 데이터를 모두 받아둠.
   
   - 어떠한 요청이 막혀도, 바로 다음 작업을 진행할 수 있기 때문에 빠른 반응속도 유도할 수 있음
   
   - 코드가 복잡해져 개발 시 어려울 수 있음

AJAX는 비동기 방식!

비동기 처리 순서

AJAX의 비동기적 처리는 XMLHttpRequest 객체를 이용하거나 Promise 방식을 사용해 진행된다.

1. XMLHttpRequest 객체를 생성하고, 요청을 초기화한다.

2. 요청을 서버로 비동기적으로 전송한다.

3. 서버로부터 응답 대기. 그동안 사용자는 페이지 다른 부분을 사용할 수 있다.

4. 응답이 도착하면 지정해둔 콜백 함수가 실행돼 응답 처리.

XMLHttpRequest 방식

XMLHttpRequest는 서버와 HTTP 통신을 가능하게 하는 객체이다.

var xhr = new XMLHttpRequest();	// 객체 생성

xhr.open("GET", "data.json", true); // 메서드와 URL 설정(초기화)

// 요청 성공 시 발생할 콜백함수를 지정
xhr.onload = function () {
	// 서버 응답 결과를 처리할 콜백함수
    if (xhr.status === 200) {
        console.log("Received: " + xhr.responseText);
    }
};
// 요청 전송
xhr.send();

Promise 방식

Promise는 비동기 작업을 더 쉽게 처리하도록 하는 객체.

동기 코드처럼 읽고 쓸수 있어 가독성도 상승함.

function fetchData() {
	// resolve : 요청 성공 시 호출할 함수
    // reject : 요청 실패 시 호출할 함수
    return new Promise((resolve, reject) => {
        var xhr = new XMLHttpRequest();
        xhr.open("GET", "data.json");
        xhr.onload = function () {
            if (xhr.status === 200) {
                resolve(xhr.responseText);
            } else {
                reject("Failed to fetch data");
            }
        };
        xhr.onerror = function () {
            reject("Network error");
        };
        xhr.send();
    });
}

fetchData().then(data => console.log(data)).catch(err => console.error(err));

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.

연속되는 모든 부분 문자열을 반복문 2개를 통해 추출하고,

중복 제거의 경우 Set을 이용해 중복을 제거했다.

시간 복잡도를 줄이고자 StringBuilder를 사용해 문자열을 담았으나,

결과적으로 950ms의 아쉬운 실행속도가 나왔다.

원인은 중복 제거 시 Set 자료구조를 사용할 때 중복을 제거하는 과정의 시간복잡도가

O(N^2)이기 때문에 시간이 오래 걸린 것으로 추측된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class S3_서로다른부분문자열의개수 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		Set<String> set = new HashSet<>();;
		
		int len = str.length();
		for (int i=0; i<len; i++) {
			StringBuilder sb = new StringBuilder();
			for (int j=i; j<len; j++) {
				sb.append(str.charAt(j));
				set.add(sb.toString());
			}
		}
		
		System.out.println(set.size());
	}
}

보완점

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String input = reader.readLine();
        int n = input.length();

        // 접미사 배열 생성
        String[] suffix = new String[n];
        for (int i = 0; i < n; i++) {
            suffix[i] = input.substring(i);
        }

        // 접미사 배열 정렬
        Arrays.sort(suffix);
        int len = 0;

        // LCP 계산
        for (int i = 1; i < n; i++) {
            int curr = 0;
            int minLen = Math.min(suffix[i].length(), suffix[i - 1].length());
            while (curr < minLen && suffix[i].charAt(curr) == suffix[i - 1].charAt(curr)) {
                curr++;
            }
            len += curr;
        }

        // 총 부분 문자열 개수에서 중복된 부분을 뺀 개수 출력
        int total = (n * (n + 1)) / 2; // 총 부분 문자열 개수
        System.out.println(total - len);
    }
}

접미사 배열을 생성하여 정렬한 뒤,

정렬된 접미사들을 앞 뒤 접미사와 비교하며 공통 접두사 길이를 계산해 중복 부분 문자열을 제거하는 방식인

LCP 알고리즘 풀이를 사용했다.

처음 보는 알고리즘 방식이라 참신하고 좋은 방법이라는 생각이 든다.

익혀놓아야 겠다.

LCP 배열 계산

1. 가능한 모든 접미사를 저장해둔다.

apple => apple, pple, ple, le, e

2. 접미사들을 사전 순으로 정렬한다.

apple, e, le, ple, pple

3. 각 접미사들을 순회하며 이전 접미사와 비교해 공통 접두사의 길이를 계산한 LCP 배열에 저장해둔다.

apple : e => 0

e : le => 0

le : ple => 0

ple : pple => 1

따라서 중복되는 경우는 총 1가지이다!

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

플로이드 워셜 알고리즘을 생각해봤지만,

시간 복잡도가 O(N^3)이고, 문제에서의 N 범위는 최대 1000이기 때문에,

해당 문제에서는 비효율적일 것이라 판단했고,

다익스트라를 사용하기로 결정하여 다익스트라 알고리즘으로 풀어냈다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static class Node implements Comparable<Node>{
        int v, w;
        public Node() {
        }
        @Override
        public String toString() {
            return "Node [v=" + v + ", w=" + w + "]";
        }
        public Node(int v, int w) {
            super();
            this.v = v;
            this.w = w;
        }
        @Override
        public int compareTo(Node o) {
            return this.w - o.w;
        }
    }
    static int N, M, X, max;
    static ArrayList<Node>[] adjList;
    static int[] dist;
    static boolean[] visited;
    public static void main(String[] args) {
        init();
        
        for (int i=1; i<=N; i++) {
            int tmp1 = dijkstra(i, X);
            int tmp2 = dijkstra(X, i);
            max = Math.max(max, tmp1+tmp2);
//            System.out.println(i+" -> "+ X + " = " + (tmp1+tmp2));
        }
        
        System.out.println(max);
    }
    
    private static int dijkstra(int start, int end) {
        int res = 0;
        
        dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        visited = new boolean[N+1];
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        
        dist[start] = 0;    // 시작점은 거리 0
        pq.add(new Node(start, 0));
        
        while(!pq.isEmpty()) {
            Node curr = pq.poll();    // 큐에서 현제 노드 뽑음
            if (curr.v == end) {
            	return dist[curr.v];
            }
            if (visited[curr.v]) continue;
            visited[curr.v] = true;
            
            // 인접 노드 탐색
            for (Node node : adjList[curr.v]) {
                // 아직 방문 안했고, 거리가 더 작으면 갱신
                if (!visited[node.v] && dist[node.v] > dist[curr.v] + node.w) {
                    dist[node.v] = dist[curr.v] + node.w;
                    pq.add(new Node(node.v, dist[node.v]));
                }
            }
//            if (visited[end]) {
//                System.out.println(Arrays.toString(dist));
//                return dist[end];
//            }
        }
        return dist[end];
    }

    private static void init() {
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        M = sc.nextInt();
        X = sc.nextInt();
        
        adjList = new ArrayList[N+1];
        for (int i=1; i<=N; i++) {
            adjList[i] = new ArrayList<>();
        }
        for (int i=0; i<M; i++) { 
            adjList[sc.nextInt()].add(new Node(sc.nextInt(), sc.nextInt()));
        }
        
        max = 0;
    }
    
    

}

다익스트라 문제를 여러번 풀었지만, 우선순위 큐를 사용하고, Node 객체를 만들어 푸는

방식의 다익스트라 구현은 계속 헷갈린다.

플로이드 워셜 알고리즘도 간단해 보이는데 생각보다 머리에 잘 들어오지 않는다.

계속해서 풀어봐야겠다!

보완점

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static class Node implements Comparable<Node> {
        int v, w;
        
        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }
        
        @Override
        public int compareTo(Node o) {
            return this.w - o.w;
        }
    }

    static int N, M, X;
    static ArrayList<Node>[] adjList;
    static int[] distFromX, distToX; // X로부터의 거리, X로 가는 거리 배열
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        init();
        
        // X에서 모든 노드로 가는 최단 거리 계산
        distFromX = dijkstra(X);
        
        int maxDist = 0;
        
        // 각 노드에서 X로 가는 최단 거리 계산 후 최대값 찾기
        for (int i = 1; i <= N; i++) {
            if (i != X) { // X에서 X로 가는 경로는 제외
                distToX = dijkstra(i); // i에서 출발해 X로 가는 거리 배열
                maxDist = Math.max(maxDist, distToX[X] + distFromX[i]);
            }
        }
        
        System.out.println(maxDist);
    }

    // 다익스트라 메서드: 시작 노드로부터 각 노드까지의 최단 거리 계산
    private static int[] dijkstra(int start) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, INF);
        PriorityQueue<Node> pq = new PriorityQueue<>();
        
        dist[start] = 0;
        pq.add(new Node(start, 0));
        
        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            
            // 현재 노드로부터 인접 노드 탐색
            for (Node next : adjList[curr.v]) {
                if (dist[next.v] > dist[curr.v] + next.w) {
                    dist[next.v] = dist[curr.v] + next.w;
                    pq.add(new Node(next.v, dist[next.v]));
                }
            }
        }
        return dist;
    }

    // 입력 및 초기화 메서드
    private static void init() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        X = sc.nextInt();
        
        adjList = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            adjList[u].add(new Node(v, w));
        }
        
        sc.close();
    }
}

1. 모든 경우에 i부터 X, X부터 i 두번 다익스트라를 사용했는데,

 X애서 i로 가는 최단경로를 미리 한번에 구한 후, i부터 X로 가는 최단거리만 계산하는 방식으로 연산량을 줄임

2. 방문 배열을 제거해도 구동에 문제가 없어 방문 배열을 제거함

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

1차 시도 (오답)

문제를 계속 째려보다 보니 위상정렬 알고리즘이 생각났다.

주어지는 입력에서 키를 비교한 입력값 각각을 간선이라고 생각하고,

앞에 오는 숫자가 시작노드, 뒤에 오는 숫자가 종점 노드가 되는 방향 그래프를 그려

나를 향하는 노드가 없는 노드부터 큐에 담아 순서대로 출력하는 그림을 그린 후 코드를 작성했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int[][] adjArr;
	static boolean[] visited;
	static StringBuilder sb;

	public static void main(String[] args) throws IOException {
		init(); // 변수 선언 및 초기화 메서드

		wisangSort();	// 위상정렬

		print(); // 출력 메서드
	}

	// 변수 선언 및 초기화 메서드
	static void init() throws IOException {
		sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken()); // 학생 수
		M = Integer.parseInt(st.nextToken()); // 학생 수

		adjArr = new int[N + 1][N + 1]; // 인접행렬
		for (int r = 0; r < M; r++) {
			st = new StringTokenizer(br.readLine());
			adjArr[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;
		} // 인접행렬 작성

		visited = new boolean[N + 1]; // 방문배열
	}

	// 위상정렬 수행 메서드
	private static void wisangSort() {
		Queue<Integer> q = new LinkedList<>();

		// 자기 자신을 향하는 노드가 없는 시작지점 노드를 큐에 삽입
		out: for (int e = 1; e <= N; e++) {
			for (int s = 1; s <= N; s++) {
				if (adjArr[s][e] > 0)
					continue out;
			}
			q.add(e);
			visited[e] = true;
		}
		
		while (!q.isEmpty()) {
			int curr = q.poll();	// 큐에서 뽑기
			sb.append(curr).append(' ');	// 스트링빌더에 추가
			
			// 인접행렬을 뒤져 아직 방문 안했으면서 인접한 노드를 큐에 삽입
			for (int i=1; i<=N; i++) {
				if (adjArr[curr][i] > 0 && !visited[i]) {
					q.add(i);
					visited[i] = true;
				}
			}
		}
	}

	// 출력 메서드
	private static void print() {
		System.out.println(sb);
	}
}

결과는 메모리 초과.

원인으로 의심되는 것들은 크게 2가지였다.

1. 방문배열을 추가적으로 선언하여 불필요한 메모리 사용

2. 인접리스트 대신 인접 행렬을 사용하여 불필요한 메모리 사용

하지만 둘 모두 수정해보아도 메모리 초과는 여전했다.

2차 시도 (정답)

결국 원인은 위상정렬을 구현하는 과정의 문제였다.

위상정렬 알고리즘을 생각한 것은 잘했지만, 구체적인 구현 방법이 생각나지 않아

내가 머리속에서 굴린 알고리즘으로만 구현했더니 통과가 안되었다.

결국 위상정렬 알고리즘을 다시 찾아보고 나서야 정답을 맞출 수 있었다.

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M;
    static List<Integer>[] adjList;
    static int[] inDegree;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        init(); // 변수 선언 및 초기화 메서드
        wisangSort(); // 위상정렬
        print(); // 출력 메서드
    }

    // 변수 선언 및 초기화 메서드
    static void init() throws IOException {
        sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 학생 수
        M = Integer.parseInt(st.nextToken()); // 비교 횟수

        adjList = new ArrayList[N + 1]; // 인접 리스트
        inDegree = new int[N + 1]; // 진입 차수

        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }

        for (int r = 0; r < M; r++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adjList[u].add(v); // u -> v 간선 추가
            inDegree[v]++; // v의 진입 차수 증가
        }
    }

    // 위상정렬 수행 메서드
    private static void wisangSort() {
        Queue<Integer> q = new LinkedList<>();

        // 진입 차수가 0인 노드를 큐에 삽입
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                q.add(i);
            }
        }

        while (!q.isEmpty()) {
            int curr = q.poll(); // 큐에서 뽑기
            sb.append(curr).append(' '); // 스트링빌더에 추가
            
            // curr와 인접한 노드들에 대해 진입 차수를 감소시키고 0이 되면 큐에 추가
            for (int neighbor : adjList[curr]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    q.add(neighbor);
                }
            }
        }
    }

    // 출력 메서드
    private static void print() {
        System.out.println(sb);
    }
}

결론은

방문배열을 사용하는 것이 아니라,

진입차수 배열을 생성하여

큐에서 꺼낸 노드와 인접한 노드들과의 간선을 1개씩 제거하며 진입차수를 떨어트리고,

진입차수가 0인 것들을 큐에 담는 과정이 필요했다...

다시한번 위상정렬 알고리즘을 공부할 수 있는 기회가 되었다.

다음에는 진입차수 배열을 사용하는 것을 잊지 말아야지!

프레임워크란?

• 개발자가 일정 규칙과 구조 안에서 코드를 작성하도록 돕는 도구
• 복잡한 로직을 단순화하거나 생략할 수 있도록 해 코드 재사용성, 유지보수성을 높임
• 객체 생성, 의존성 관리 등 잡다한 부분을 자동화하여 필요한 비즈니스 로직에 집중할 수 있게 해준다. (생산성 증가)

Spring 프레임워크 특징

1. POJO (Plain Old Java Object)
   특별한 인터페이스나 클래스를 상속받지 않고 순수한 자바 객체를 사용해 개발 진행한다.
   이는 코드 재사용성, 독립성을 높임
   
   
2. 의존성 주입
   의존성 주입을 통해 객체 간 결합도를 낮춘다.
   
   
3. AOP (관점 지향 프로그래밍)
   횡단 관심사 분리(Cross-Cutting Concerns)하여 핵싱 기능들이 수행될 때 수반해야할 부수 기능들을 모듈화할 수 있도록 도움
   
   
4. 트랜잭션 관리
   선언적 트랜잭션 관리를 통해 데이터의 무결성, 안정성을 유지할 수 있게 돕는다!
   메서드가 수행되다가 예외가 발생하면 메서드 실행 전 상태로 데이터 상태를 복원해준다.

의존성 주입이란?

객체가 필요한 의존성을 직접 생성하지 않고, 외부 다른 클래스에서 주입받는 방식.

특정 구현체에 고정되지 않고, 다양한 구현체로 쉽게 변경이 가능해 유연성이 높아지고,

다른 환경에서도 재사용하기 쉽기 때문에 재사용성이 좋아진다.

의존관계 역전

상위 클래스가 하위 클래스에 의존하지 않고 인터페이스나 추상 클래스에 의존하도록 함으로써, 상위 모듈이 하위 모듈 변화에 영향을 덜 받도록 하는 방식

이 방식은 코드 유연성과 확장성을 높이고 의존성을 쉽게 관리할 수 있다.

// 인터페이스
public interface PaymentService {
    void processPayment();
}

// 인터페이스를 구현한 클래스 A
public class CreditCardPaymentService implements PaymentService {
    @Override
    public void processPayment() {
        System.out.println("Processing credit card payment...");
    }
}

// 주문서비스
public class OrderService {
	// 인터페이스에 의존
    private PaymentService paymentService;
	
    // 결제서비스를 신용카드 대신 현금으로 교체해도 해당 코드를 수정하지 않아도 됨!
    public OrderService(PaymentService paymentService) {
        this.paymentService = paymentService;
    }

    public void placeOrder() {
        System.out.println("Placing order...");
        paymentService.processPayment();
    }
}

위 코드에서 OrderService는 PaymentService 인터페이스에 의존하므로, 실제 구현을 쉽게 변경할 수 있음. CreditCardPaymentService 대신 다른 결제 서비스로 교체해도 OrderService의 코드는 수정할 필요가 없어진다!

Spring에서 의존성을 주입하는 방법

1. XML설정 파일을 통한 방법

<!-- applicationContext.xml -->
<beans xmlns="http://www.springframework.org/schema/beans" ...>
    <bean id="paymentService" class="com.example.CreditCardPaymentService"/>
    <bean id="orderService" class="com.example.OrderService">
        <constructor-arg ref="paymentService"/>
    </bean>
</beans>

2. 어노테이션을 이용한 방법

@Service
public class OrderService {
    private final PaymentService paymentService;

    @Autowired
    public OrderService(PaymentService paymentService) {
        this.paymentService = paymentService;
    }

    public void placeOrder() {
        System.out.println("Placing order...");
        paymentService.processPayment();
    }
}

3. Java Config를 통한 방법

@Configuration
public class AppConfig {
    @Bean
    public PaymentService paymentService() {
        return new CreditCardPaymentService();
    }

    @Bean
    public OrderService orderService() {
        return new OrderService(paymentService());
    }
}

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

50 10 100 20 40
30 50 70 10 60

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

import java.util.Scanner;

public class S1_스티커 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {

			int n = sc.nextInt();
			int[][] stickers = new int[2][n + 1];
			int[][] dp = new int[2][n + 1];
			for (int i = 0; i < 2; i++) {
				for (int j = 1; j <= n; j++) {
					stickers[i][j] = sc.nextInt();
				}
			}

			dp[0][1] = stickers[0][1];
			dp[1][1] = stickers[1][1];

			// 1. 현재 칸 스티커를 떼는 경우
			// 1-1) 이전 칸 스티커를 떼는 경우
			// 1-2) 이전 칸 스티커를 떼지 않는 경우
			// 2. 현재 칸 스티커를 뗴지 않는 경우 -> 이전 칸을 무조건 뗌
			for (int i = 2; i <= n; i++) {
				// 0행의 값 계산
				int max0 = 0;
				// 1번 경우
				max0 = Math.max(stickers[0][i] + Math.max(dp[0][i - 2], dp[1][i - 2]), stickers[0][i] + dp[1][i - 1]);
				// 2번 경우
				max0 = Math.max(max0, Math.max(dp[0][i - 1], dp[1][i - 1]));
				// 대입
				dp[0][i] = max0;

				// 1행 값 계산
				int max1 = 0;
				// 1번 경우
				max1 = Math.max(stickers[1][i] + Math.max(dp[0][i - 2], dp[1][i - 2]), stickers[1][i] + dp[0][i - 1]);
				// 2번 경우
				max1 = Math.max(max1, Math.max(dp[0][i - 1], dp[1][i - 1]));
				// 대입
				dp[1][i] = max1;
			}
			
			System.out.println(Math.max(dp[0][n], dp[1][n]));
		}
	}
}

보완 사항

import java.util.Scanner;

public class S1_스티커 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            int n = sc.nextInt();
            int[][] stickers = new int[2][n + 1];
            int[] dp = new int[n + 1];

            for (int i = 0; i < 2; i++) {
                for (int j = 1; j <= n; j++) {
                    stickers[i][j] = sc.nextInt();
                }
            }

            if (n == 1) {
                System.out.println(Math.max(stickers[0][1], stickers[1][1]));
                continue;
            }

            dp[1] = Math.max(stickers[0][1], stickers[1][1]);
            dp[2] = Math.max(stickers[0][2] + stickers[1][1], stickers[1][2] + stickers[0][1]);

            for (int i = 3; i <= n; i++) {
                dp[i] = Math.max(dp[i - 2] + Math.max(stickers[0][i], stickers[1][i]), dp[i - 1]);
            }

            System.out.println(dp[n]);
        }
    }
}

• 기존엔 2차원 배열을 선언해 1행과 2행 모두 고려하여 계산했지만, 그럴 필요가 없이 1행짜리 배열로도 계산이 가능했다. 

DP문제를 풀 때 고려하지 않아도 되는 사항을 최대한 생각해 작업속도를 줄여야겠다.

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class G5_치킨배달 {
	static class Chicken {
		int r, c;

		public Chicken() {
		}

		public Chicken(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

		@Override
		public String toString() {
			return "Chicken [r=" + r + ", c=" + c + "]";
		}
	}

	static int N, M, min;
	static int[][] map;
	static int[][] tmpMap;
	static boolean[][] visited;
	static ArrayList<Chicken> chickens;
	static Chicken[] pick;
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();

		min = Integer.MAX_VALUE; // 치킨 거리의 최소값을 저장할 변수

		map = new int[N][N];
		tmpMap = new int[N][N];
		visited = new boolean[N][N];
		chickens = new ArrayList<>(); // 치킨집 좌표를 담을 리스트
		pick = new Chicken[M]; // M개를 뽑은 후 저장할 배열

		// 맵 입력 및 치킨집 탐색
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				map[r][c] = sc.nextInt();
				if (map[r][c] == 2) {
					chickens.add(new Chicken(r, c));
					map[r][c] = 0; // 지도상으로는 0으로 초기화
				}
			}
		}
		pick(0, 0);
		
		System.out.println(min);
	}

	private static void pick(int n, int r) {
		// 모두 골랐으면 탐색 시작
		if (r >= M) {
			editMap();
			int tmpDist = search();
			if (min > tmpDist) {
				min = tmpDist;
			}
			return;
		}
		// 남은 치킨집 수보다 골라야 할 치킨집 수가 많으면 부적절하므로 종료
		if (n >= chickens.size()) {
			return;
		}

		// 해당 치킨집을 안고른다
		pick(n + 1, r);
		// 해당 치킨집을 고른다
		pick[r] = chickens.get(n);
		pick(n + 1, r + 1);
	}

	// 선택한 치킨집만 지도상에 2로 표시
	private static void editMap() {
		for (int r=0; r<N; r++) {
			tmpMap[r] = map[r].clone();
		}
		for (Chicken chicken : pick) {
			tmpMap[chicken.r][chicken.c] = 2;
		}
	}

	// 지도 탐색하여 집일 경우 BFS탐색하여 거리 계산
	private static int search() {
		int sum = 0;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				if (tmpMap[r][c] == 1) {
					int dist = BFS(r, c);
					sum += dist;
				}
			}
		}
		return sum;
	}

	private static int BFS(int r, int c) {
		Queue<int[]> q = new LinkedList<>();

		int dist = 0;
		int size = 1;
		visited = new boolean[N][N];

		visited[r][c] = true; // 시작지점 방문체크
		q.add(new int[] { r, c }); // 큐에 삽입

		while (!q.isEmpty()) {

			for (int i = 0; i < size; i++) {
				int[] curr = q.poll();
				// 치킨집이면 탐색 종료
				if (tmpMap[curr[0]][curr[1]] == 2) {
					return dist;
				}
				// 4방탐색
				for (int dir = 0; dir<4; dir++) {
					int nr = curr[0] + dr[dir];
					int nc = curr[1] + dc[dir];
					
					if (nr<0 || nr>=N || nc<0 || nc>=N || visited[nr][nc]) continue;
					
					q.add(new int[] {nr, nc});
					visited[nr][nc] = true;
				}
			}
			size = q.size();
			dist += 1;
		}
		
		return dist;
	}
}

public class G5_치킨배달 {
	static class Chicken {
		int r, c;

		public Chicken() {
		}

		public Chicken(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

		@Override
		public String toString() {
			return "Chicken [r=" + r + ", c=" + c + "]";
		}
	}
	static class House {
		int r, c;
		public House() {
			// TODO Auto-generated constructor stub
		}
		public House(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		@Override
		public String toString() {
			return "House [r=" + r + ", c=" + c + "]";
		}
	}
	static int N, M, min;
	static int[][] map;
	static ArrayList<Chicken> chickens;
	static ArrayList<House> houses;
	static Chicken[] pick;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();

		min = Integer.MAX_VALUE; // 치킨 거리의 최소값을 저장할 변수

		map = new int[N][N];
		chickens = new ArrayList<>(); // 치킨집 좌표를 담을 리스트
		houses = new ArrayList<>(); // 집 좌표를 담을 리스트
		pick = new Chicken[M]; // M개를 뽑은 후 저장할 배열

		// 맵 입력 및 치킨집 탐색
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				map[r][c] = sc.nextInt();
				if (map[r][c] == 2) {
					chickens.add(new Chicken(r, c));
					map[r][c] = 0; // 지도상으로는 0으로 초기화
				} else if (map[r][c] == 1) {
					houses.add(new House(r, c));
				}
			}
		}
		pick(0, 0);
		
		System.out.println(min);
	}

	private static void pick(int n, int r) {
		// 모두 골랐으면 탐색 시작
		if (r >= M) {
			int tmpDist = search();
			if (min > tmpDist) {
				min = tmpDist;
			}
			return;
		}
		// 남은 치킨집 수보다 골라야 할 치킨집 수가 많으면 부적절하므로 종료
		if (n >= chickens.size()) {
			return;
		}

		// 해당 치킨집을 안고른다
		pick(n + 1, r);
		// 해당 치킨집을 고른다
		pick[r] = chickens.get(n);
		pick(n + 1, r + 1);
	}

	// 모든 집 탐색하며 선택한 각 치킨집과의 최소 거리를 구해 마을의 총 치킨거리 계산
	private static int search() {
		int sum = 0;
		for (House h : houses) {
			int tmpMin = Integer.MAX_VALUE;
			for (Chicken c : pick) {
				tmpMin = Math.min(Math.abs(h.r-c.r)+Math.abs(h.c-c.c), tmpMin);
			}
			sum += tmpMin;
		}
		return sum;
	}
}

복습 사항

배열 깊은 복사(deep copy)

깊은복사는 배열의 주소값이 아닌 실제 값을 복사하는 것을 말함

일반적으로 copyArr = originArr 의 방식으로 복사하면 원본 배열의 주소값이 복사되기 떄문에,

copyArr의 값을 수정하면 originArr의 값도 같이 변한다!

따라서 깊은 복사가 필요할 땐 아래와 같이 할 것

int[][] newMap = new int[N][N];
for (int i = 0; i < N; i++) {
    newMap[i] = map[i].clone();  // 각 행을 개별적으로 복사
}