[BAEKJOON] 18405번 : 경쟁적 전염 (JAVA)

2024. 6. 9. 01:18· BE/Java
반응형

- 알고리즘 분류 : 구현

- 사용 언어 : JAVA

- 문제 요점

    - 바이러스의 번호가 낮은 순서부터 퍼트리면 된다.

    - 필자는 우선순위 큐와 큐를 이용해서 풀었다.

    - 소스에 보면 결국엔 큐를 이용해서 푸는데 그 이유로는, 우선순위 큐로도 가능하지만 우선순위큐에 넣게되면 넣을 때마다 정렬을 하기 때문에 큐에다가 넣은 것.

 

 

소스 설명은 주석을 참고해주세요.

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

public class Main {

	// N : 시험관의 크기, K : 가장 높은 바이러스의 번호 
	public static int N, K;
	
	// 맵
	public static int[][] map;
	
	// 상하좌우 퍼지는 데 사용될 배열들
	public static int[] xmove = {-1,1,0,0};
	public static int[] ymove = {0,0,-1,1};

	// 바이러스의 위치를 담을 큐
	public static Queue<Virus> q = new LinkedList<>();
	
	// 바이러스 클래스 
	public static class Virus implements Comparable<Virus>{
		int y;
		int x;
		int rank;
		
		public Virus(int y, int x, int rank) {
			this.y = y;
			this.x = x;
			this.rank = rank;
		}

		@Override
		public int compareTo(Virus o) {
			// TODO Auto-generated method stub
			if(this.rank < o.rank) {
				return -1;
			}
			else {
				return 1;
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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];
		
		// 우선순위큐에 넣어서 낮은 바이러스부터 정렬되도록 함
		PriorityQueue<Virus> pq = new PriorityQueue<>();
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				int num = Integer.parseInt(st.nextToken());
				map[i][j] = num;
				
				// 바이러스일 때만 넣어줌
				if(num != 0) {
					pq.offer(new Virus(i, j, num));
				}
			}
		}
		
		// 우선순위 큐에 있던 내용들(정렬되어있음)을 일반 큐로 복사
		while(!pq.isEmpty()) {
			Virus v = pq.poll();
			q.offer(v);
		}
		
		st = new StringTokenizer(br.readLine());
		int endTime = Integer.parseInt(st.nextToken());
		int endY = Integer.parseInt(st.nextToken()) - 1; 	
		int endX = Integer.parseInt(st.nextToken()) - 1;
		
		// 주어진 초만큼 반복
		for(int i=0; i<endTime; i++) {
			Queue<Virus> q2 = new LinkedList<>();
			
			// q에 있던 걸 q2로 옮기고
			while(!q.isEmpty()) {
				Virus v = q.poll();
				q2.offer(v);
			}
			
			// q2에 있는 것을 모두 탐색
			while(!q2.isEmpty()) {
				// q2에서 꺼낸 바이러스를
				Virus v = q2.poll();
				
				// 상하좌우 확산시키기
				Spread(v);
			}
		}
		
		// 결과 출력
		System.out.println(map[endY][endX]);
	}
	
	// 바이러스 확산
	public static void Spread(Virus v) {
		// 상하좌우 탐색
		for(int i=0; i<4; i++) {
			int tempY = v.y + ymove[i];
			int tempX = v.x + xmove[i];
			
			// 맵의 범위를 벗어나면 무시
			if(tempY < 0 || tempY >= N || tempX < 0 || tempX >= N) {
				continue;
			}else {
				int vRank = map[tempY][tempX];
				
				// 이동할 곳에 바이러스가 아직 없다면
				if(vRank == 0) {
					// 바이러스 퍼트리고
					map[tempY][tempX] = v.rank;
					
					// q에다가 넣기
					q.offer(new Virus(tempY, tempX, v.rank));
				}
			}
		}
	}

}
반응형

'BE > Java' 카테고리의 다른 글

[Java] Reflection?  (0) 2024.12.16
MapStruct 예제 및 리스트 매핑  (0) 2024.07.07
[JMeter] JMeter 사용 및 설치 방법  (0) 2024.05.06
[Java 8] Stream, 데이터 리듀싱  (1) 2024.03.24
[Java 8] 람다식과 함수형 인터페이스  (0) 2024.03.10
'BE/Java' 카테고리의 다른 글
  • [Java] Reflection?
  • MapStruct 예제 및 리스트 매핑
  • [JMeter] JMeter 사용 및 설치 방법
  • [Java 8] Stream, 데이터 리듀싱
멍목
멍목
개발 관련 새롭게 알게 된 지식이나 좋은 정보들을 메모하는 공간입니다.
반응형
멍목
김멍목의 개발블로그
멍목
전체
오늘
어제
  • 분류 전체보기 (514)
    • BE (190)
      • Spring (21)
      • Java (141)
      • Kotlin (6)
      • JPA (22)
    • FE (33)
      • Javascript (16)
      • Typescript (0)
      • React (5)
      • Vue.js (9)
      • JSP & JSTL (3)
    • DB (32)
      • Oracle (22)
      • MongoDB (10)
    • Algorithm (195)
    • Linux (8)
    • Git (6)
    • etc (42)
    • ---------------------------.. (0)
    • 회계 (4)
      • 전산회계 2급 (4)
    • 잡동사니 (2)

블로그 메뉴

  • 홈
  • 관리

공지사항

인기 글

태그

  • 자기공부
  • 이펙티브자바
  • 자기개발
  • Effective Java
  • 자기 개발
  • MongoDB 기초부터 실무까지
  • 자바 공부
  • 자기 공부
  • 자바공부
  • 코테 공부
  • java 8
  • MongoDB with Node.js
  • Java to Kotlin
  • 이펙티브 자바
  • 더 자바 Java 8
  • Oracle
  • 프로젝트로 배우는 Vue.js 3
  • vue3 공부
  • JPA 공부
  • JPA
  • 알고리즘공부
  • 코테공부
  • junit5
  • MongoDB 공부
  • 자바 테스팅 프레임워크
  • 코틀린
  • 알고리즘 공부
  • 자바 개발자를 위한 코틀린 입문
  • 전산회계 2급 준비
  • 더 자바 애플리케이션을 테스트하는 다양한 방법

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
멍목
[BAEKJOON] 18405번 : 경쟁적 전염 (JAVA)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.