developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 삼성코테자바풀이
  • 카카오코테
  • c++디자인패턴
  • c++ 빌더 패턴
  • 삼성코테구현문제추천
  • 삼성코테자바준비
  • 삼성코테기출자바풀이
  • 코테파이썬
  • 삼성코테준비
  • MA모형
  • 시계열분석
  • 삼성코테파이썬준비
  • 통계분석
  • 시계열
  • Arima
  • SW역량테스트파이썬풀이
  • AR모형
  • 삼성코테자바꿀팁
  • 삼성코테구현풀이
  • 백준파이썬풀이
  • 통계학
  • 카카오코테java풀이
  • 데이터분석
  • 삼성코테파이썬풀이
  • BOJ파이썬풀이
  • 삼성코테기출
  • 운영체제인터럽트
  • 삼성코테파이썬
  • SW역량테스트파이썬
  • ARIMA모형

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 마법사 상어와 파이어볼 20056번 (JAVA)

2022. 4. 30. 14:00

❓ 문제 - 백준 마법사 상어와 파이어볼 20056번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/20056)

 

20056번: 마법사 상어와 파이어볼

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치

www.acmicpc.net

 

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

  • Node로 각 파이어볼의 ArrayList<Node> map의 2차원배열로 파이어볼의 위치를 관리한다.
  • 각 파이어볼의 이동처리는 동시에 일어나므로 map_copy를 활용해서 파이어볼의 이동처리를 구현한다.
  • 0번 행과 n-1행이 연결되어 있고, 0번 열이 n-1번 열과 연결되어 있으므로 하나의 파이어볼에 방향에 맞춰 속력s로 이동할 때 속력 s를 n으로 나눈 나머지로 nx, ny를 구한다. 만약 nx, ny가 0보다 작다면 n을 더해주고, nx, ny가 n보다 크거나 같다면 n을 빼준다. 원하는 방향으로 이동가능 하다.
  • 만약에 한 곳에 여러 파이어볼이 이동하여 위치했다면 파이어볼의 질량, 속력, 방향을 주어진 식대로 구해주고, check1로 현재 위치에 존재하는 파이어볼이 모두 홀수인지 체크하고, check2로 현재 위치에 존재하는 파이어볼이 모두 짝수인지 체크해준다. 그리고 다 더한 질량의 합을 5로 나누었을 때 0보다 크지 않다면 소멸 처리, 아니면 해당 조건에 맞춰 4개의 파이어볼로 나누는 처리를 한다.

 

💻 소스코드

// BOJ - 마법사 상어와 파이어볼 (20056번)
// 구현

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

public class Main_20056 {
	public static int n, m, k;

	public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
	public static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
	public static ArrayList<Node>[][] map;
	
	public static class Node {
		int x;
		int y;
		int m;
		int d;
		int s;
		public Node(int x, int y, int m, int d, int s) {
			this.x = x;
			this.y = y;
			this.m = m;
			this.d = d;
			this.s = s;
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		map = new ArrayList[n][n];
		
		
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			if(map[x-1][y-1] == null) {
				map[x-1][y-1] = new ArrayList<Node>();
				map[x-1][y-1].add(new Node(x-1, y-1, m, d, s));
			} else {
				map[x-1][y-1].add(new Node(x-1, y-1, m, d, s));
			}
		}
		
		while(k-- > 0) {
			// 파이어볼 이동
			ArrayList<Node>[][] map_copy = new ArrayList[n][n];
			
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(map[i][j] == null) continue;
					for(int p=0;p<map[i][j].size();p++) {
						Node node = map[i][j].get(p);

						int nx = node.x + dx[node.d] * (node.s % n);
						int ny = node.y + dy[node.d] * (node.s % n);
		
						if(nx < 0) {
							nx = n - Math.abs(nx);
						} else if(nx >= n) {
							nx -= n;
						}
						if(ny < 0) {
							ny = n - Math.abs(ny);
						} else if(ny >= n) {
							ny -= n;
						}
			
						
						if(map_copy[nx][ny] == null) {
							map_copy[nx][ny] = new ArrayList<>();
						} 
						map_copy[nx][ny].add(new Node(nx, ny, node.m, node.d, node.s));
					}
				}
			}
			
			// 중복 처리
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(map_copy[i][j] == null || map_copy[i][j].size() == 1) {
						continue;
						
					}
					int sum_m = 0;
					int sum_s = 0;
					int size = map_copy[i][j].size();
					boolean check1 = true; // 홀수 체크
					boolean check2 = true; // 짝수 체크
					for(int p=0;p<map_copy[i][j].size();p++) {
						Node nd = map_copy[i][j].get(p);
						sum_m += nd.m;
						sum_s += nd.s;
						if(nd.d % 2 == 1) {
							check2 = false;
						} else {
							check1 = false;
						}
					}
					map_copy[i][j].clear();
					if(sum_m / 5 != 0) {

						for(int p=0;p<4;p++) {
							int dir = 0;
							if(check1 || check2) {
								dir = p*2;
							} else {
								dir = p*2+1;
							}
							map_copy[i][j].add(new Node(i, j, sum_m/5, dir, sum_s/size));
						}
					} 
				}
			}
			map = map_copy;
		}
		
		int ans = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(map[i][j] == null) continue;
				for(int p=0;p<map[i][j].size();p++) {
					ans += map[i][j].get(p).m;
				}
			}
		}
		System.out.println(ans);
	}

}

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 마법사 상어와 파이어스톰 20058번 (JAVA)  (0) 2022.04.30
BOJ - 마법사 상어와 토네이도 20057번 (JAVA)  (0) 2022.04.30
BOJ - 컨베이어 벨트 위의 로봇 20055번 (JAVA)  (0) 2022.04.30
BOJ - 스타트택시 19238번 (JAVA)  (0) 2022.04.30
BOJ - 어른 상어 19237번 (JAVA)  (0) 2022.04.30
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 마법사 상어와 파이어스톰 20058번 (JAVA)
    • BOJ - 마법사 상어와 토네이도 20057번 (JAVA)
    • BOJ - 컨베이어 벨트 위의 로봇 20055번 (JAVA)
    • BOJ - 스타트택시 19238번 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바