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

이번 글을 통해 배워갈 내용
- 백준 18405번 풀이
https://www.acmicpc.net/problem/18405
18405번: 경쟁적 전염
첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치
www.acmicpc.net
백준 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;
}
}
}
읽어주셔서 감사합니다
무엇인가 얻어가셨기를 바라며
오늘도 즐거운 코딩 하시길 바랍니다 ~ :)
728x90
'Java > Java 알고리즘' 카테고리의 다른 글
| 백준 25304번 영수증 JAVA 구현해보기 (0) | 2022.06.27 |
|---|---|
| 백준 10833번 사과 JAVA 구현해보기 (0) | 2022.06.25 |
| 백준 9375번 패션왕 신해빈 JAVA 구현해보기 (0) | 2022.06.19 |
| 백준 10816번 숫자카드 JAVA 구현해보기 (0) | 2022.06.19 |
| 백준 1932번 정수 삼각형JAVA 구현해보기 (0) | 2022.06.18 |