본문 바로가기

백준

[백준] 21611번 - 마법사 상어와 블리자드 (Java) ⬛ 문제 https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net ⬛ 풀이 삼성 SW 역량 테스트 기출 문제이다. 구현량이 많은 시뮬레이션 문제라 풀다가 토나올 뻔 했다... 입력은 2차원 배열이지만 달팽이 모양을 일렬로 펼쳐 1차원으로 생각하고 풀었다. 프로그램 전체 로직은 다음과 같다. 1. 처음에 달팽이 모양으로 input을 탐색하여 map을 1차원 배열로 저장한다. 2. 4방향의 블리자드 인덱스들을 2차원 배열(bzIdx)로 계.. Algorithm/백준 2021. 10. 6.
[백준] 1194번 - 달이 차오른다, 가자 (Java) ⬛ 문제 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net ⬛ 풀이 지난번 풀이한 백준 1600번 - 말이 되고픈 원숭이와 유사한 문제였다. 다만 6개의 키 보유 현황을 저장해야하기 때문에 비트마스킹이 추가로 필요했다. 프로그램 전체 로직은 다음과 같다. 1. BFS를 사용하며, 비트마스킹을 통해 현재 키 보유 상태를 관리한다. 2. 최대키 개수는 6개이므로 방문관리를 boolean[64][N][M] 3차원 배열로 .. Algorithm/백준 2021. 10. 6.
[백준] 1600번 - 말이 되고픈 원숭이 (Java) ⬛ 문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net ⬛ 풀이 BFS와 DP를 접목한 문제이다. 한 번쯤 익혀놓으면 좋은 문제였다. 프로그램 전체 로직은 다음과 같다. 1. 3차원 배열 visited를 사용해 방문 체크와 경로 거리를 저장한다. 2. visited는 [k+1][h][w] 크기로 생성하고 각각 말 이동을 0회~k회 한 H x W 크기의 배열로 볼 수 있다. 3. BFS를 사용해 목적지까지 최단 경로를 찾고 기존.. Algorithm/백준 2021. 9. 16.
[백준] 17144번 - 미세먼지 안녕! (Java) ⬛ 문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net ⬛ 풀이 시뮬레이션 문제이다. 모든 먼지들을 동시에 확산시키는 부분이 핵심인 문제였던 것 같다. 프로그램 전체 로직은 다음과 같다. 1. 기존 map과 별개로 spread[][] 라는 임시 공간을 만들어 확산된 먼지들을 더해놓는다. 2. 모든 먼지 확산이 끝나면 map과 spread를 합치고 spread 공간을 0으로 초기화시켜준다. 3. 먼지확산 + 공기청정기 가동을 1cycle로 놓.. Algorithm/백준 2021. 9. 15.
[백준] 17472번 - 다리 만들기2 (Java) ⬛ 문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net ⬛ 풀이 최소신장트리(MST) 문제이다. 프로그램 전체 로직은 다음과 같다. 1. bfs를 사용해 섬 별로 번호를 붙여 country[][]를 생성한다. 2. country[][]를 탐색하여 0이 아닐 시(섬이면) 4방을 탐색하고 만약 0이라면 해당 섬의 가장자리라는 뜻이다. 3. 해당방향으로 다리 생성을 시도하고 성공한다면 Bridge를 생성하여 pq에 삽입한다. .. Algorithm/백준 2021. 9. 15.
[백준] 1992번 - 쿼드트리 (Java) ⬛ 문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net ⬛ 풀이 기본적인 분할-정복 문제이다. 영역을 탐색하여 하나라도 다른 숫자가 있다면 4개의 영역으로 분할한다. 다시 그 영역들은 좌측 상단 좌표부터 시작하여 탐색을 시작하고 또 그중에서 다른 숫자가 있다면 4개의 영역으로 분할한다. 만약 영역 사이즈가 1이라면 더 이상 분할하지 않고 해당 문자를 출력한다. ⬛ 코드 import java.io.BufferedReader; imp.. Algorithm/백준 2021. 8. 22.
[백준] 11559번 - Puyo Puyo (Java) ⬛ 문제 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net ⬛ 풀이 BFS를 활용한 시뮬레이션 문제이다. 프로그램 전체 로직은 다음과 같다. 1. 이차원 배열 map을 탐색 중 R, G, B, P, Y 라면 상하좌우를 체크하고 같은 색이라면 탐색 큐에 추가한다. 2. 큐에 추가할 때 방문 체크를 해놓고, 탐색 길이가 4 이상이라면 탐색한 좌표들을 '.'으로 바꾼다. (터뜨리기) 3. 끝까지 탐색을 완료하면 chain 카운.. Algorithm/백준 2021. 8. 15.
[백준] 1068번 - 트리 (Java) ⬛ 문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net ⬛ 풀이 얼핏보면 주어진 입력대로 트리를 구성하고, DFS를 통해 리프노드 갯수를 구하는 단순한 문제이다. 하지만 문제 어디에도 입력 트리가 이진 트리라는 말도, 입력 값이 오름차순이라는 말도, 루트가 하나라는 전제도 없다. (물론 이번 문제는 루트는 하나이다.) 초반에 입력이 오름차순일 것이라고 가정하여 IndexOutOfBounds를 줄기차게 먹었다;; 프로그램 전체 로직은 다음.. Algorithm/백준 2021. 8. 15.
728x90
반응형

티스토리툴바