'알고리즘/BOJ' 카테고리의 글 목록 (2 Page)

[BOJ] 20058 마법사 상어와 파이어스톰 - Java

2024.03.01

✨ BFS + 구현 ➔ 부분 격자를 시계방향으로 90도 회전 https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 📍 고려해야할 점 2^L * 2^L 크기의 부분 격자로 나누고 모든 부분 격자를 시계방향으로 90도 회전 L=1일 때, 2x2의 부분격자가 시계방향으로 90도 회전 L=2일 때, 4x4의 부분격자가 시계방향으로 90도 회전 (x, y)칸에서 인접한 칸(상하좌우) 중 얼음이 있는 칸이 3개 미만이면 (x, y)칸 얼음의..

알고리즘/BOJ

[BOJ] 21609 상어 중학교 - Java

2024.02.26

✨ 구현 & BFS https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 📍 고려해야할 점 그룹에 속하는 블록의 조건 일반 블록이 적어도 하나 이상 일반 블록의 색은 모두 같아야함 검은색 블록 포함 X 무지개색 블록은 몇개든 상관 X 블록의 개수는 2개 이상 블록 그룹의 기준 블록 = 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록. 그러한 블록이 여러 개이면 열의 번호가 가장 작은 블록 .. 오토플레이 기능 ➔ 블록 그룹이 없을 때..

알고리즘/BOJ

[BOJ] 1018 체스판 다시 칠하기 - Java

2023.12.05

✨ 브루트포스 ➔ 완전탐색 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 📍 고려해야할 점 주어진 체스판을 8x8 크기의 체스판으로 만들어야 한다. 흰색과 검은색이 번갈아서 칠해져있어야 한다. (0, 0)이 검은색인 경우와 흰색인 경우를 나누어서 구한다. 가로, 세로 인덱스 값의 합이 짝수, 홀수에 따라 흰색인지 검은색인지 구분해서 구한다. 🕹️ 풀이 과정 1️⃣ 주어진 체스판을 8x8 크기로 다시 만들어야 하기 때문에 copy배열을 ..

알고리즘/BOJ

[BOJ] 1504 특정한 최단 경로 - Java

2023.12.05

✨ 다익스트라 ➔ 최단경로 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 📍 고려해야할 점 방향이 없는 그래프이다. 1번 정점에서 N번 정점으로 최단거리로 이동한다. 주어진 두 정점을 반드시 거쳐야 한다. 두 정점이 v1, v2라면 1 ➔ v1 ➔ v2 ➔ N 또는 1 ➔ v2 ➔ v1 ➔ N 두가지 방법으로 이동할 수 있다. 🕹️ 풀이 방법 1️⃣ 노드에 대한 정보 (이동해야하는 노드 = v, 해..

알고리즘/BOJ

[BOJ] 18352 특정 거리의 도시 찾기 - Java

2023.12.04

✨ 그래프 탐색 ✨ BFS, 다익스트라 ➔ 최단 경로 찾기 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 📍 고려해야할 점 출발 도시에 대한 정보가 존재한다. 최단 거리에 대한 정보가 존재한다. ➔ 해당하는 최단 거리인 도시를 찾으면 된다. 하나의 도시에서 다른 모든 도시까지의 최단거리를 구해야하기 때문에 다익스트라 알고리즘을 사용한다. 도시간의 거리가 모두 1이기 때문..

알고리즘/BOJ

[BOJ] 4179 불! - Java

2023.10.25

✨ BFS ➔ 동시에 이동시키기 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 📍 고려해야할 점 불과 지훈이를 동시에 이동시켜야한다. 동시에 이동시키기 위해서 두 개의 큐를 사용한다. 불은 지훈이의 존재 여부에 대해 영향을 받지 않는다. (지훈이가 있거나 없어도 언제든지 벽만 아니라면 언제든지 전파 가능) 지훈이는 불의 존재 여부에 대해 영향을 받는다. (불이 존재한다면 이동 불가) 지훈이가 가장자리에 도달하면 미로를 통과할 ..

알고리즘/BOJ

[BOJ] 14502 연구소 - Java

2023.09.28

✨ BFS + DFS + 완전탐색 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 📍고려해야할 점 벽을 3개 세운다. ➔ 일일이 3개의 벽을 세워본 후 바이러스를 퍼뜨려 안전영역이 최대인 경우를 구한다. (백트래킹 + 완전탐색) 벽을 3개 세운 후 바이러스가 퍼지는 경우는 다양하므로 복사본을 만들어서 구한다. 🕹️ 풀이과정 1️⃣ 바이러스와 벽이 있는 곳의 정보를 2차원 배열에 저장한다. 2️⃣ 벽을 세운다. ➔ 3개의 벽을 세워야 하므로 조합을 생각하면 ..

알고리즘/BOJ

[BOJ] 3190 뱀

2023.09.25

✨ 구현 ➔ '큐' 이용하기 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 📍 고려해야할 점 자료구조 '큐'의 특성을 이용해서 풀기 뱀의 머리를 먼저 이동시켜 몸길이 늘리기 해당하는 칸에 사과가 있으면 사과를 먹고 사과를 없애주기 뱀의 꼬리가 아닌 몸통을 만나면 끝내기 ➔ return !! 벽에 닿으면 끝내기 ➔ return !! 뱀은 (1, 1)에 존재 행, 열 잘 구분하기 ! 방향 바꿀 때 효율적인 방법 생각해보기 🕹️ 풀이과정 1️⃣ 행, 열에..

티스토리툴바