백준 18405번 경쟁적 전염 JAVA 구현해보기

---

```

백준 18405번 경쟁적 전염 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1. 백준 18405번 풀이

---

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

18405번: 경쟁적 전염

 

 

백준 18405번 경쟁적 전염은

난이도 골드 등급의 문제로서

 

NXN에 시험관 속에 

바이러스들이 주어지고

먼저 지역을 선점한 바이러스는 대체할 수 없고

각 바이러스는 숫자가 작은 순으로 1초에 한 번씩 상하좌우로 늘어난다고 할 때

위치 P 가 주어지면 해당 위치에 N 초 뒤에 바이러스가 있는지 확인하고

있다면 해당 위치를 차지한 바이러스를 출력하면 되는 문제입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

BFS로 풀어도 되나

모든 바이러스를 비교해서

최단거리를 가지며 같은 거리인 경우 숫자가 적은 바이러스를 찾아주고

주어진 시간보 다작 다면 해당 바이러스의 수를 출력하면 되는 문제입니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        final String[] firstLineInput = br.readLine().split(" ");
        final int mapSize = Integer.parseInt(firstLineInput[0]);

        List<Position> virusPosList = new ArrayList<>();

        for (int i = 0; i < mapSize; i++) {
            String[] nthLineInput = br.readLine().split(" ");
            for (int j = 0; j < mapSize; j++) {
                int posState = Integer.parseInt(nthLineInput[j]);
                if (posState != 0) {
                    virusPosList.add(new Position(i, j, posState));
                }
            }
        }

        String[] lastLineInput = br.readLine().split(" ");
        final int timePassed = Integer.parseInt(lastLineInput[0]);
        final int row = Integer.parseInt(lastLineInput[1]) - 1;
        final int col = Integer.parseInt(lastLineInput[2]) - 1;

        // 연산
        // 모든 바이러스와 시작점과의 거리를 구한다
        virusPosList.forEach(pos -> pos.distance = Math.abs(pos.col - col) + Math.abs(pos.row - row));

        // 시작점과의 최소거리를 가진 바이러스를 찾는다
        Position nearestPos = virusPosList.stream().reduce((posA, posB) -> {
            if (posA.distance < posB.distance) {
                return posA;
            } else if (posA.distance > posB.distance) {
                return posB;
            } else {
                if (posA.state < posB.state) {
                    return posA;
                } else {
                    return posB;
                }
            }
        }).get();

        // 시작점과 최소거리를 가진 바이러스가 있다면 출력한다.
        int retVal = 0;
        if (nearestPos.distance <= timePassed) {
            retVal = nearestPos.state;
        }
        System.out.print(retVal);
    }

    public static class Position {
        int row;
        int col;
        int state;
        int distance;

        public Position(int row, int col, int state) {
            this.row = row;
            this.col = col;
            this.state = state;
        }


    }

}

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---