시뮬레이션

📖 문제 https://www.acmicpc.net/problem/10431   💡  풀이 방식• 시뮬레이션1. TC 번호와 20개의 숫자를 입력받는다.2. 각 학생들에 대해 본인 앞에 있는 본인보다 키 큰 사람 수를 구한다. ⇒ 시간 복잡도 : O(TC * N^2) 🔺 코드123456789101112131415161718192021222324252627282930313233343536import java.util.*;import java.io.*; public class Main {    static int T, P;        public static void main(String[] args) throws IOException {        BufferedReader br = new Buf..

📖 문제 https://www.acmicpc.net/problem/10709   💡  풀이 방식• 구현1. 2차원 배열에 구역 값을 입력받는다.2. 각 행을 돌며 각 (i,j)가 몇 분 뒤 처음으로 하늘에 구름이 오는지를 확인한다.  - 현재 i번째 행의 j번째 열에 구름이 있는 경우> dist[i][j] = 0, 현재 열 j를 변수로 저장한다.  - 현재 i번째 행의 j번째 열에 구름이 없는 경우> 앞 열에서 구름이 있었다면, (현재 열 - 가장 가까운 구름 열)의 값을 dist[i][j]에 저장한다.  🔺 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556im..

📖 문제 https://www.acmicpc.net/problem/12100   💡  풀이 방식• 백트래킹 + 시뮬레이션 백트래킹으로 상하좌우 4방향에 대해 5회까지 다 이동시켜보고, 배열 내 가장 큰 수를 구한다.  🔸 void DFS(명령 횟수)[종료 조건] 명령 횟수가 5번인 경우, 배열 내 최댓값을 탐색하고, 이를 최댓값과 비교해 최댓값 갱신if(cnt == 5) { findMax(); return;} 그게 아닌 경우, 과정 1,2를 진행한다. 1) 원본 배열 map을 복사한다.int[][] copy = copyArray(map); 2) 상하좌우 4방향 중 이동 방향을 정하고, 해당 방향으로 이동시키고, 명령 횟수에 +1해 재귀호출을 진행한다. 그리고 이동시켰던 배열 값을 원상복구..

📖 문제 https://www.acmicpc.net/problem/15683  💡  풀이 방식• 시뮬레이션 + 백트래킹 + 브루트포스  각 CCTV의 타입을 받아, 각 타입에 맞춰 회전된 상태를 조합해 사각지대의 최소값을 구한다.CCTV 타입이 1( → )인 경우 : 북(0 / ↑), 남(1 / ↓), 서(2 / ←), 동(3 / →)CCTV 타입이 2( ↔ )인 경우 : 서동(23 / ↔), 북남(01 / ↕ )CCTV 타입이 3(↑→)인 경우 : 북동(03 / ↑→) , 남동(13 / ↓→) , 남서(12 / ↓←) , 북서(02 / ←↑)CCTV 타입이 4( ←↑→ )인 경우 : 북서동(023), 북남동(013), 남서동(123), 북남서 (012)CCTV 타입이 5(↕↔)인 경우 : 북남서동(..

📖 문제 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 💡 풀이 방식 • BFS + 시뮬레이션 1. 배열을 시계 방향으로 90도 회전시킨다. (그림 참고) private static void rotate(int r, int c, int v, int[][] tmp) {// tmp : 회전 후 값 저장용 배열 for(int i = 0 ; i < v; i++) { for(int j = 0 ; j < v ; j++) { tmp[r + i][c + j] = A[r + v - 1 - j][c + i]..

📖 문제 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 💡 풀이 방식 • BFS 필요 자료구조 - 로봇 객체 (행, 열, 방향, 명령 횟수) - 3차원 boolean형 방문 표시 배열 : [행][열][방향] ⭐ - dx/dy 배열 동서남북 배열 1. 격자를 입력받는다. 2. 시작점 위치,방향과 도착점 위치,방향을 입력받는다. String[] s1 = br.readLine().split(" "); start = new Robot(Integer.parseInt(s1[0]) -1, Integer.parseInt(s1[1])..

📖 문제 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 💡 풀이 방식 • 구현, 시뮬레이션 필요 자료구조 - 인접한 4방향 탐색용 dx/dy배열 - 폭탄 터질 시간 기록용 2차원 배열 timeArr ⭐ - 폭탄이 터질 시간나타내는 int형 변수 time (⚠ 1부터 시작!!) 1. 격자를 입력받으면서, 폭탄인 경우 폭탄 터질 시간을 기록한다. if(board[i][j] == 'O') timeArr[i][j] = 3; // 폭탄 터질 시간 (놓인 시간 +3) 2. 0초에는 아무 것도 하지 않고, 1초: 가만히 있음 > 2초: 폭..

📖 문제 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 💡 풀이 방식 • 시뮬레이션 + BFS 1. 크기가 가장 큰 블록 그룹을 찾는다. → BFS static Block findMaxBlockGroupe() { visited = new boolean[N][N]; Block maxBlock = new Block(0, 0, EMPTY, Integer.MIN_VALUE, Integer.MIN_VALUE); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) ..

📖 문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡 풀이 방식 • BFS 인구 이동이 가능하지 않을 때까지 인구 이동을 진행한다. (while문)→ 완전탐색을 통해 격자 내의 모든 점에 대해 인구 이동이 가능한지 확인한다. (move 메소드) → 모든 점에 대해 4방향 탐색하며인접한 나라와 국경선이 열려있다면, 해당 나라에서 이동하며 연합한다. (BFS) - 이동 및 연합 가능한 나라는 방문한 적 없고, 두 나라 간 인구 수 차이가 L이상 R이하인 나라여야 한다. - 조건을 만족하는 인접..