상어의 식사

류한선·2025년 6월 23일

실기연습-2

목록 보기

32/95

좋아요! 백준 1671번, **상어의 저녁식사 문제**를 자세히 다뤄보겠습니다.
이 문제를 정리해 드리고, 예제 입출력과 정답 코드(Java), 그리고 한 줄 한 줄 디버깅 수준의 자세한 해설을 준비할게요.

📝 문제 요약

여러 상어가 있는데, 상어는 다른 상어를 잡아먹을 수 있습니다. 상어의 정보 (크기, 속도, 지능)가 주어질 때:

상어 A가 상어 B를 잡아먹을 수 있는 조건:

상어 A가 상어 B보다 크기, 속도, 지능이 모두 크거나 같으면 잡아먹을 수 있다.

만약 상어의 정보가 완전히 같으면, 번호가 낮은 상어가 높은 상어를 잡아먹을 수 있다.

목표: 잡아먹히지 않고 살아남을 수 있는 상어의 최소 수를 출력.

🧪 예제 입출력

📥 예제 입력

📤 예제 출력

💡설명:

5마리의 상어가 있고, 각 상어의 (크기, 속도, 지능) 정보가 주어집니다.
(9,8,7)은 가장 크므로 다른 상어를 잡아먹을 수 있다.
(3,3,3)도 (2,2,2) 또는 (1,2,3)을 잡아먹을 수 있다.
이렇게 잡아먹을 수 있는 관계를 최대한 계산해보면 남는 상어 수가 2마리임을 알 수 있다.

🎯 풀이 아이디어 (간략)

이분 매칭(Bipartite Matching) 문제로 바꿀 수 있다.
- 각 상어를 잡을 수 있는 상어와의 관계를 그래프로 만든다.
- 상어마다 잡아먹을 수 있는 상어가 있으면 간선을 연결한다.
최대 유량 또는 이분 매칭을 이용해 최대 잡아먹을 수 있는 쌍을 찾는다.
살아남을 수 있는 상어 수 = N - 최대 매칭 수.

⚙️ 자바 정답 코드

이 문제를 **자바(Java)**로 해결해 보겠습니다.
그리고 한 줄 한 줄 디버깅 수준의 아주 자세한 설명을 곁들일게요!

💻 전체 코드

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

class Shark {
    int size, speed, intel;
    Shark(int s, int sp, int i) {
        this.size = s;
        this.speed = sp;
        this.intel = i;
    }
}

public class Main {
    static int N;
    static Shark[] sharks;
    static ArrayList<Integer>[] graph;
    static int[] match;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine().trim());  // 상어 수 N을 읽음

        sharks = new Shark[N];  // 상어 정보를 담을 배열
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            int s = Integer.parseInt(input[0]);
            int sp = Integer.parseInt(input[1]);
            int i2 = Integer.parseInt(input[2]);
            sharks[i] = new Shark(s, sp, i2);  // 상어 정보 초기화
        }

        graph = new ArrayList[N];  // 그래프 초기화
        for (int i = 0; i < N; i++) graph[i] = new ArrayList<>();

        // 잡아먹을 수 있는 경우의 수를 그래프로 연결
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j) continue;
                if (canEat(sharks[i], sharks[j], i, j)) {  // i가 j를 잡아먹을 수 있는가?
                    graph[i].add(j);  // 간선 연결
                }
            }
        }

        match = new int[N];  // 잡아먹히는 상대를 표시
        Arrays.fill(match, -1);  // -1로 초기화

        int result = 0;  // 최대 잡아먹을 수 있는 쌍 수
        for (int i = 0; i < N; i++) {
            for (int k = 0; k < 2; k++) {  // 같은 상어가 2번 잡을 수 있게 함
                visited = new boolean[N];  // 방문 초기화
                if (dfs(i)) result++;
            }
        }

        System.out.println(N - result);  // 살아남은 상어 수 출력
    }

    static boolean canEat(Shark a, Shark b, int i, int j) {
        // a가 b를 잡아먹을 수 있는지 검사
        if (a.size >= b.size && a.speed >= b.speed && a.intel >= b.intel) {
            // 완전히 동일한 경우에는 index가 낮은 쪽이 잡아먹음
            if (a.size == b.size && a.speed == b.speed && a.intel == b.intel && i > j) {
                return false;
            }
            return true;
        }
        return false;
    }

    static boolean dfs(int node) {
        if (visited[node]) return false;  // 이미 방문한 경우 false 반환
        visited[node] = true;             // 현재 정점을 방문 표시

        for (int next : graph[node]) {
            if (match[next] == -1 || dfs(match[next])) {
                // next를 아직 안 잡았거나 이미 잡힌 상어를 다른 상어가 잡을 수 있으면
                match[next] = node;
                return true;
            }
        }
        return false;
    }
}

🔍 코드 줄단위 해설 (예제 입력 대입하여 디버깅하기)

이 부분은 초보자 눈높이에 맞춰 한 줄 한 줄 디버깅 느낌으로 자세히 씁니다.

💡 우리가 위의 예제 입력(5\n1 2 3\n2 2 2\n2 2 2\n3 3 3\n9 8 7\n)을 넣고 디버깅해봅시다.

주요 부분 디버깅 및 설명

상어 정보 읽기

N = Integer.parseInt(br.readLine().trim());

N=5. 상어 수를 읽습니다.

sharks = new Shark[N]; 
for (int i = 0; i < N; i++) {
    ...
    sharks[i] = new Shark(s, sp, i2); 
}

i=0일 때 sharks[0] = (1,2,3),
i=1일 때 sharks[1] = (2,2,2) ... 이렇게 차례대로 5마리 채웁니다.

먹을 수 있는 관계 그래프 연결

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (i==j) continue;
        if (canEat(sharks[i], sharks[j], i, j)) {
            graph[i].add(j);
        }
    }
}

상어 i가 상어 j를 잡을 수 있으면 graph[i].add(j).
예를 들어, 상어 4번(9,8,7)은 0~3번을 다 잡아먹을 수 있습니다.
상어 3번(3,3,3)도 상어 0~2를 잡을 수 있습니다.

이분 매칭

for (int i = 0; i < N; i++) {
    for (int k = 0; k < 2; k++) {
        visited = new boolean[N]; 
        if (dfs(i)) result++;
    }
}

한 상어당 최대 두 번 잡아먹을 수 있는 점을 이용하기 위해 k=0,1 두 번 돌아봄.
dfs(i)로 먹을 수 있는 상대 찾기.

dfs 구현

static boolean dfs(int node) {
    if (visited[node]) return false;
    visited[node] = true;
    for (int next : graph[node]) {
        if (match[next] == -1 || dfs(match[next])) {
            match[next] = node;
            return true;
        }
    }
    return false;
}

아직 잡히지 않았거나 다른 잡아먹을 수 있는 상어를 바꿀 수 있으면 매칭.

출력

System.out.println(N - result);

N에서 잡힌 수를 빼면 남은 수.

🎯 정리

✅ 위의 코드와 같이 동작하면, 남은 상어 수(2)가 출력되며 문제의 정답과 일치합니다.

좋아요! 🎯
지금 보고 계신 부분은, 입력값을 한 줄씩 읽고 각 상어의 크기(s), 속도(sp), 지능(i2)을 Shark 객체에 담아 sharks` 배열에 채우는 부분이에요.

이 부분을 실제 예제 입력을 가지고 디버깅해 볼게요.

🧪 예제 입력

🐞 디버깅 단계별 상황

상어 수 N = 5

우리는 i = 0부터 i = 4까지 루프를 돌며 br.readLine() → split() → parseInt() → sharks[i] = new Shark(...)를 하게 됩니다.

🔍 i = 0

br.readLine() → "1 2 3"
input = ["1","2","3"]
s = 1, sp = 2, i2 = 3
sharks[0] = new Shark(1,2,3);

🐟 sharks[0]: { size=1, speed=2, intel=3 }

🔍 i = 1

br.readLine() → "2 2 2"
input = ["2","2","2"]
s = 2, sp = 2, i2 = 2
sharks[1] = new Shark(2,2,2);

🐟 sharks[1]: { size=2, speed=2, intel=2 }

🔍 i = 2

br.readLine() → "2 2 2"
input = ["2","2","2"]
s = 2, sp = 2, i2 = 2
sharks[2] = new Shark(2,2,2);

🐟 sharks[2]: { size=2, speed=2, intel=2 }

🔍 i = 3

br.readLine() → "3 3 3"
input = ["3","3","3"]
s = 3, sp = 3, i2 = 3
sharks[3] = new Shark(3,3,3);

🐟 sharks[3]: { size=3, speed=3, intel=3 }

🔍 i = 4

br.readLine() → "9 8 7"
input = ["9","8","7"]
s = 9, sp = 8, i2 = 7
sharks[4] = new Shark(9,8,7);

🐟 sharks[4]: { size=9, speed=8, intel=7 }

📜 sharks 배열 상태 정리

Index	size	speed	intel
0	1	2	3
1	2	2	2
2	2	2	2
3	3	3	3
4	9	8	7

이렇게 sharks 배열이 채워지며, 나중에 canEat 검사나 매칭할 때 이용하게 됩니다.

좋아요! 🎯 이번엔 아래 부분을 예제 데이터를 바탕으로 한 줄 한 줄 디버깅해보겠습니다.

🔍 우리가 가진 상어들 정리

앞서 정리한 대로:

Index	size	speed	intel
0	1	2	3
1	2	2	2
2	2	2	2
3	3	3	3
4	9	8	7

🧠 canEat(a,b,i,j) 조건 정리

이 함수의 핵심:

if (a.size >= b.size && a.speed >= b.speed && a.intel >= b.intel) {
    // 모두 크거나 같으면 잡아먹을 수 있음
    // 단, (a,b) 완전히 동일하다면 index가 낮은 쪽만 잡아먹을 수 있음
}

🐞 이중 for 디버깅 시작

i = 0

j = 1:
(1,2,3) vs (2,2,2)
size: 1 >= 2 ? ❌ → 잡아먹을 수 없음
j = 2: (동일) ❌
j = 3: (1,2,3) vs (3,3,3) ❌
j = 4: (1,2,3) vs (9,8,7) ❌
👉 graph[0]에는 아무것도 안 들어감.

i = 1

j = 0:
(2,2,2) vs (1,2,3)
size 2≥1 OK, speed 2≥2 OK, intel 2≥3 ❌ → 잡아먹을 수 없음
j = 2:
(2,2,2) vs (2,2,2)
완전 같음.
index i=1 > j=2? 아니고 i=1 < j=2이므로 잡아먹을 수 있음 ✅
→ graph[1].add(2);
j = 3: (2,2,2) vs (3,3,3) ❌
j = 4: (2,2,2) vs (9,8,7) ❌
👉 graph[1] = [2]

i = 2

j = 0:
(2,2,2) vs (1,2,3)
intel 2≥3 ❌ → 잡아먹을 수 없음
j = 1:
(2,2,2) vs (2,2,2)
완전 같음. i=2 > j=1 ? OK → 잡아먹을 수 있음 ✅
→ graph[2].add(1);
j = 3: (2,2,2) vs (3,3,3) ❌
j = 4: (2,2,2) vs (9,8,7) ❌
👉 graph[2] = [1]

i = 3

j = 0:
(3,3,3) vs (1,2,3)
size OK, speed OK, intel OK → 잡아먹을 수 있음 ✅
→ graph[3].add(0);
j = 1:
(3,3,3) vs (2,2,2) OK OK OK → 잡아먹을 수 있음 ✅
→ graph[3].add(1);
j = 2: (3,3,3) vs (2,2,2) OK OK OK → 잡아먹을 수 있음 ✅
→ graph[3].add(2);
j = 4: (3,3,3) vs (9,8,7) ❌
👉 graph[3] = [0,1,2]

i = 4

j = 0,1,2,3 전부 검사: (9,8,7) vs 나머지 상어들
크기, 속도, 지능 모두 4번 상어가 크므로:
→ graph[4].add(0);
→ graph[4].add(1);
→ graph[4].add(2);
→ graph[4].add(3);
👉 graph[4] = [0,1,2,3]

📜 최종 graph 구조

i	graph[i] (먹을 수 있는 상어 목록)
0	[]
1	[2]
2	[1]
3	[0,1,2]
4	[0,1,2,3]

💡 한 줄 한 줄 정리

이중 for 루프:

i==j 건너뛴다.
canEat() 조건 검사:
- 모든 수치가 크거나 같으면 잡아먹을 수 있음.
- 완전히 같을 경우 index 낮은 쪽만 잡아먹을 수 있음.
graph[i].add(j)로 관계 저장.

이 정보는 나중에 이분 매칭(DFS) 단계에서 누가 누구를 잡을 수 있는지를 탐색할 수 있게 합니다.

좋아요! 🎯 이제 dfs(int node) 메서드를 예제 상황을 기준으로 한 줄 한 줄 디버깅해 드릴게요.
이 부분은 **이분 매칭 알고리즘(Bipartite Matching)**의 핵심 부분이라, “잡아먹기 쌍”을 찾아가는 과정을 디버깅 느낌으로 아주 자세히 보여드릴 거예요.

🔍 `dfs(node)` 함수의 역할

이 함수의 목적:

현재 node가 잡을 수 있는 상어들(graph[node] 안의 원소들) 중,
아직 잡히지 않았거나(match[next] == -1),
이미 잡힌 상어(match[next] != -1)를 다른 상어에게 넘길 수 있으면,
node가 next를 잡도록 연결(match[next] = node)하고 true 반환!

🔄 상태 정리 (예제에서 dfs 호출하기 전에 상태)

graph[0] = []
graph[1] = [2]
graph[2] = [1]
graph[3] = [0,1,2]
graph[4] = [0,1,2,3]

그리고 초기에:

match = [-1, -1, -1, -1, -1];  // 아무도 안 잡힌 상태
visited = new boolean[N];     // dfs 호출마다 false로 초기화

🎮 이제 dfs 호출을 따라가봅시다.

1️⃣ `dfs(1)` 호출

visited[1] = false에서 시작
visited[1] = true; 표시
graph[1] = [2], 그러므로 next = 2 검사
- match[2] == -1 → 아직 안 잡힘!
- 그래서 match[2] = 1로 잡기 등록
dfs(1) 반환값 = true
👉 상어 1이 상어 2를 잡음!

2️⃣ `dfs(2)` 호출

visited[2] = false에서 시작
visited[2] = true;
graph[2] = [1], next = 1 검사
- match[1] == -1 → 아직 안 잡힘
- match[1] = 2; 등록
반환 true
👉 상어 2가 상어 1 잡음!

3️⃣ `dfs(3)` 호출

visited[3] = false에서 시작
visited[3] = true;
graph[3] = [0,1,2] 검사 시작
1. next = 0
  - match[0] == -1 → 안 잡혔으니 잡기
  - match[0] = 3; 등록
  - 반환 true
    👉 상어 3이 상어 0 잡음!

4️⃣ `dfs(4)` 호출

visited[4] = false에서 시작
visited[4] = true;
graph[4] = [0,1,2,3] 검사 시작
1. next = 0
  - match[0] == 3 (이미 상어 3이 잡고 있음)
  - dfs(match[0]) = dfs(3) 호출
    - 하지만 visited[3]을 dfs 호출 직전에 false로 초기화하기 때문에 dfs(3)에서 검사
    - visited[3] = true; 설정
    - graph[3] 검사 → (0,1,2)
      - next=0 → 이미 잡음, dfs(3) 안에서 dfs(3) 호출되므로 visited[3]=true라 false
      - next=1 → match[1]=2 → dfs(2) 호출
        
        visited[2]=true; → dfs(2) false 반환
      - next=2 → match[2]=1 → dfs(1) 호출
        
        visited[1]=true; → dfs(1) false 반환
    - dfs(3)에서 잡을 수 있는 다른 경로 없음 → false 반환
  - dfs(3) false 반환 받았으므로 next=0에서 실패
2. next = 1
  - match[1] == 2 잡힌 상태
  - dfs(2) 호출 → visited[2]=false 초기화된 상태
    - visited[2]=true; graph[2]=[1]
      - next=1 → match[1]=2 → dfs(2) 호출 (재귀) → visited[2]=true여서 false 반환
    - dfs(2) 반환 false
  - 잡기 실패
3. next = 2
  - match[2] == 1 잡힌 상태
  - dfs(1) 호출
    - visited[1]=false 초기화된 상태
    - visited[1]=true; graph[1]=[2]
      - next=2 → match[2]=1 → dfs(1) 호출 (재귀) → visited[1]=true라 false
    - dfs(1) 반환 false
4. next = 3
  - match[3] == -1 아직 안 잡힘
  - match[3]=4; 등록하고 true 반환

👉 상어 4가 상어 3 잡음!

🔄 요약

이 dfs() 함수는:

이미 잡힌 상어를 다른 상어에게 떠넘길 수 있는 경로를 찾고,
그 경로가 있으면 연결을 바꿔 주며 true 반환.

이 과정을 통해 최대 잡아먹을 수 있는 쌍을 확장하게 되고,
최종적으로 match 배열의 잡힌 수만큼 살아남지 않는 상어 수가 계산됩니다.

🎯 이렇게 디버깅을 해보면 dfs의 역할을 이해하기 좋아요:

현재 node가 잡을 수 있는 후보들(next)에 대해 검사
이미 잡혔으면 잡힌 상어의 기존 소유자(match[next])를 다른 곳으로 옮길 수 있는지 dfs 호출
옮기기 성공 시 현재 node가 next를 잡도록 연결
실패하면 다른 next 검사
다 검사해도 못 잡으면 false 반환

좋은 질문이에요! 🎯
이건 이분 매칭의 특성 때문인데, 하나씩 잘 짚어드릴게요.

✏️ 요점을 미리 정리:

dfs(node)에서 graph[node] 안의 next를 하나씩 검사하다가, next가 이미 다른 상어에게 잡혔으면, 그 상어(match[next])가 다른 곳을 잡을 수 있는지를 재귀(dfs(match[next]))로 탐색해봄.
이전 상어들(dfs(1), dfs(2), dfs(3))에서는 대부분 "빈 자리(match[next] == -1)"를 바로 잡아서 재귀 호출이 적었고,
dfs(4) 때는 이미 많은 상어가 잡힌 상태여서 잡히지 않은 자리(-1)가 거의 없음 → 기존 잡힌 상어를 다른 자리로 옮겨주기 위해 dfs()를 여러 번 호출하게 된 거예요.

🧠 이해하기 쉬운 비유:

예를 들어:

1번, 2번, 3번 상어가 각각 다른 상어를 잡아둠.
이제 4번 상어가 "잡을 수 있는 후보들"을 검사해보는데, 후보들이 전부 이미 잡혀있음.
그러면 4번 상어가 잡으려면, 잡힌 상어의 기존 소유자(match[next])가 다른 걸 잡도록 자리 비우기를 부탁해야 함.
그래서 dfs(match[next])를 호출하여 "혹시 다른 걸 잡을 수 있나?"를 물어보는 거죠.

🔍 이전 호출에서는 재귀가 적었던 이유

dfs(1) 호출 → 아직 아무도 안 잡혔으니 바로 잡고 끝.
dfs(2) 호출 → 아직 한 자리 안 잡혔으니 바로 잡고 끝.
dfs(3) 호출 → 한 자리 안 잡혔으니 바로 잡고 끝.

이렇게 초반에는 match[next] == -1 상황이 많았어요.

🔍 dfs(4) 호출에서 많은 재귀가 일어나는 이유

dfs(4) 호출할 때쯤이면 match[] 대부분 채워져 있음.
검사하는 next마다 match[next] != -1이므로,
"잡힌 쪽을 밀어낼 수 있나?"를 확인하기 위해 dfs(match[next]) 호출을 여러 번 하게 됨.
자리 뺏기를 연쇄적으로 시도하면서 트리 형태로 깊이 들어가요.

💡 정리

이번 호출이 유난히 많은 재귀를 하는 건, 잡을 자리가 거의 남지 않아 이미 잡힌 상어의 자리를 다른 상어로 밀어내야만 하기 때문이에요.
그래서 dfs가 연속 호출되며 깊게 탐색하게 되는 거죠.

류한선

good

이전 포스트

circuits

다음 포스트