Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 분할정복
- dfs
- 카카오
- 인텔리제이 에러
- java leetcode
- daily challenge
- 구현
- 백준 16935
- 자바 리트코드
- leetcode
- 스프링 에러
- BFS
- 스택
- java 프로그래머스
- 그래프 자바
- 프로그래머스 java
- 자바 5464
- 백준
- 백준 18222
- 프로그래머스
- 코테
- 자바
- 코딩테스트
- 리트코드
- DP
- Java
- 리트코드 1557
- 파이썬
- 리트코드 자바
- leetcode 1721
Archives
- Today
- Total
레벨업 일지
[Java] 백준 18405 경쟁적 전염 본문
문제
https://www.acmicpc.net/problem/18405
풀이
수학 문제를 풀 때 1 부터 n 까지의 수를 for문을 돌리면서 누적합을 하고 싶은가? 아님 n까지의 수의 합 n*(n+1)/2 으로 한 번에 도출 하겠는가? 당연히 후자일 것이다.
public int getSum(int n){
int sum = 0 ;
for(int i = 1; i < n+1 ;i++)
sum += i;
return sum;
}
public int getSum_fast(int n){
return n*(n+1)/2;
}
getSum() 은 O(N) , getSum_fast는 O(1) 의 시간복잡도를 가진다.
BFS 로 구현한 코드가 많은데, 이 문제의 특징은 1초에 거리 1 만큼 증가하는 것을 볼 수있다. 이 특징을 이용할 것이다.
바이러스의 위치 P1 , 알고싶은 target 위치 P2 의 거리를 구하면 bfs 탐색을 하지 않고 답을 구할 수 있다.
로직은 다음과 같다.
1. 우선 주어진 map을 탐색해서 map[i][j] > 0 이 되는 바이러스의 위치를 구한다.
2. 각 바이러스의 위치에서 목표 target (x,y) 까지의 거리를 구한다.
3. 거리가 S 이하이면 우선순위 큐에 넣는다.
4. 모든 바이러스를 탐색하고 나면 큐에서 하나 뺴서 답을 도출한다.
5. 큐 사이즈가 0 이면 0 리턴.
내가 푼 로직의 핵심
두 점의 거리를 수학적으로 구하자!
다음과 같이 두 점 사이의 거리를 수학적으로 구할 수 있따.
public int getDistance(int sX,int sY, int eX, int eY){
//start 는 2사분면, end 는 4사분면 으로 정규화.
if(sX == eX)return Math.abs(sY - eY);
else if(sY == eY) return Math.abs(sX - eX);
else{
if(sX < eX && sY > eY)sY -= (sY - eY)*2;
else if(sX > eX && sY < eY)sX -= (sX - eX)*2;
}
return Math.abs((sX + sY ) - (eX + eY));
}
코드
import java.io.*;
import java.util.*;
public class Main {
int n,k,s,x,y;
int [][] map;
public static void main(String args[]) throws IOException {
Main m = new Main();
m.sol();
}
public long getN(){
int ret =0 ;
// { index, value }
PriorityQueue<int []> pq = new PriorityQueue<>((a,b)-> a[1]-b[1] == 0 ? a[0]-b[0] : a[1]-b[1]);
for(int i =0 ;i < n ;i++){
for(int j= 0 ;j < n ;j++){
if(map[i][j] > 0){
int d = getDistance(i,j,x,y);
if(d <= s){
pq.offer(new int[]{map[i][j], d});
}
}
}
}
return pq.size()> 0 ? pq.poll()[0] : 0;
}
public int getDistance(int sX,int sY, int eX, int eY){
//start 는 2사분면, end 는 4사분면 으로 정규화.
if(sX == eX)return Math.abs(sY - eY);
else if(sY == eY) return Math.abs(sX - eX);
else{
if(sX < eX && sY > eY)sY -= (sY - eY)*2;
else if(sX > eX && sY < eY)sX -= (sX - eX)*2;
}
return Math.abs((sX + sY ) - (eX + eY));
}
public void sol() throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
map = new int[n][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());
}
}
st = new StringTokenizer(br.readLine());
s= Integer.parseInt(st.nextToken());
x= Integer.parseInt(st.nextToken())-1;
y = Integer.parseInt(st.nextToken())-1;
System.out.println(getN());
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[Java] 백준 15686 치킨 배달 (0) | 2023.02.14 |
---|---|
[Java] 백준 2839. 설탕 배달 (0) | 2023.02.03 |
[Java/Python] 백준 11501 주식 (0) | 2023.01.19 |
[Java] 백준 1700번 멀티탭 스케줄링 (0) | 2023.01.19 |
[Java/Python3] 백준 25947. 선물할인 (2) | 2023.01.18 |
Comments