본문 바로가기

algorithm

백준 21611 - 마법사 상어와 블리자드
백준 21611 - 마법사 상어와 블리자드 2025. 1. 27. 문제 : https://www.acmicpc.net/problem/21611문제 요약1. 맵의 가운데에 상어가 있고, 맵은 달팽이 모양으로 이루어져 있다.2. 맵 가운데의 상어는 먼저 구슬을 s 개 만큼 d 방향으로 파괴한다.예를들어, 아래와 같이 ↓ 방향으로 2개 만큼 구슬을 파괴할 수 있다. 3. 파괴된 이후 구슬을 앞당긴다.4-1. 구슬 번호가 4개 연속해서 같다면, 구슬의 연쇄 폭발을 발생시킨다.4-2. 파괴된 이후 구슬을 앞당긴다.4-3. 폭발이 일어났다면 4-1~2를 반복한다.5. 구슬을 그룹화 한다. 연속된 번호의 구슬들에 대해 2칸씩 차지하게 되며, 각각 개수, 번호 가 된다. 풀이 과정0. 먼저 맵의 형태가 달팽이 모양이기 때문에, 일반 배열 형태에 매칭시킨 후 진행하는 것이 편리할 것이..
백준 19236 - 청소년 상어
백준 19236 - 청소년 상어 2025. 1. 5. 문제 : https://www.acmicpc.net/problem/19236문제 요약1. 4x4 공간이 주어지며 1~16 번호를 가진 물고기가 한칸에 하나씩 존재한다.2. 각 물고기는 방향을 가지고 있으며, 1~16 순서대로 이동한다.2-1. 물고기가 이동할 수 없다면(상어가 존재 or 범위를 벗어남) 이동할 수 있을때까지 반시계 회전한다.2-2. 물고기가 이동하는 곳에 다른 물고기가 있다면 서로 위치를 바꾼다.3. 상어는 처음에 (0,0)에 있는 물고기를 먹고 시작한다.3-1. 상어는 빈 공간에 이동할 수 없으며, 물고기를 먹으면 물고기의 방향을 가진다. 위 과정을 반복하여 상어가 먹은 물고기의 번호를 더한 값의 최댓값을 구하는 것이 목표이다. 풀이 과정해당 문제는 상어가 이동하는 곳이 정해져 있지 않..
백준 17825 - 주사위 윷놀이
백준 17825 - 주사위 윷놀이 2024. 12. 30. 문제 : https://www.acmicpc.net/problem/17825문제 요약1. 시작 칸에 말 4개가 위치한다.2. 말을 하나씩 선택하여 화살표 방향대로 움직이며, 파란색 지점에 도달하면 경로를 변경한다.3. 총 10번 움직이며 1~5 칸 까지 랜덤으로 움직일 수 있다.3-1. 단, 이동한 곳에 이미 다른 말이 존재하면 이동할 수 없다. (도착점은 예외) 4. 말이 이동할때마다 칸에 적힌 점수가 추가되며 최댓값을 구해보자. 풀이 과정해당 문제는 구현 + DFS를 통해 모든 경우의 수를 탐색하여 해결했다.각 파란색 지점은 이동 경로가 변경되는 변곡점으로, 윷놀이 배열에서 따로 저장한다. 단, 25,30,35,40,도착 구간은 이동 경로가 변경되더라도 겹치는 구간이기 때문에, 해당 칸에 말이 존재하..
백준 17141 - 연구소 2 2024. 12. 10. 문제 : https://www.acmicpc.net/problem/17141 문제 요약1. 연구소에 바이러스 M개를 놓아야 하며, 바이러스를 놓을 칸이 M 2. 입력값 중 1은 벽이므로 이동할 수 없고, 모든 빈칸에 바이러스를 퍼뜨리는데 걸리는 최소 시간을 구하는 문제이다.풀이과정1. 값을 입력받을 때 바이러스를 놓을 수 있는 칸(2) 를 미리 저장해놓고, 빈칸의 개수를 미리 구해놓는다.값이 2여도 바이러스가 놓여져 있는 칸은 아니며, 빈칸으로 생각해야 한다.1-1. 만약 빈칸이 0이라면 0을 출력하고 마무리한다. for(int i=0; i 2. 바이러스를 M개만큼 선택해서 바이러스를 퍼뜨려야 한다. 이때 재귀호출하여 조합을 통해 아래와 같이 M개를 선택하고 bfs를 실행한다.void solutio..
백준 4179 - 불! (C++) 2024. 11. 9. 문제 : https://www.acmicpc.net/problem/4179 풀이과정지훈이가 불을 피해서 미로의 가장자리로 이동할 수 있는지 판단하는 문제이다.먼저 불을 전부 확산시키고 지훈이가 이동할 수 있는지 확인할 수 있도록 bfs를 2번 실행시키면 해결할 수 있다.  ! 주의할 점으로, 매번 불을 확산시키고 지훈이가 이동 가능한지 확인하는 것을 반복하면 시간초과가 발생한다.최대 arr[1000][1000] 배열에서 bfs를 50~100번 정도 실행하면 1초를 넘길 수 있기 때문이다.풀이1. 먼저 불을 확산시키며 위치마다 몇분이 걸리는지도 확인한다.불은 여러곳에 존재할 수 있기 때문에 deque에 전부 넣어놓고 bfs를 실행하여 visited 배열에 걸리는 시간을 저장한다.void fireMap() ..
백준 13549 - 숨바꼭질 3 2024. 11. 3. 문제 : https://www.acmicpc.net/problem/13549 풀이과정현재 위치 (N) 에서 -> 목적지 (K) 까지 도달하는 가장 빠른 시간을 구하는 문제이다.걸리는 시간, 즉 가중치가 1 또는 0 이므로 0-1너비우선탐색 을 사용하여 풀이할 수 있다.  풀이1. 0초 후 2*X로 이동하는 것이 가능하기 때문에너비우선탐색 시 2*X의 경우 push_front를 통해 가장 먼저 탐색할 수 있도록 한다. 2. 1초 후 X-1 또는 X+1 로 이동할 수 있으며, 0초보다 오래 걸리기 때문에너비우선탐색 시 push_back을 통해 나중에 탐색하도록 한다. 위 과정을 반복하면 최소 시간을 구할 수 있다. 코드#include #include #include using namespace std;int..
백준 7569 - 토마토 2024. 10. 20. 문제 : https://www.acmicpc.net/problem/7569 풀이과정NxMxH 3차원 배열을 입력받아, 이미 익은 토마토를 저장 후 bfs 탐색을 진행하면 해결할 수 있다.+ 이때 익지않은 토마토의 개수를 미리 세어주면 나중에 불필요한 탐색을 진행하지 않아도 된다. 풀이1. 익은 토마토의 위치를 전부 저장한다.동시에 익지 않은 토마토의 개수를 unripes 변수에 저장한다.// 높이, 세로, 가로deque > > dq;if(tomato[i][j][k] == 1) dq.push_back({i,{j,k}});else if(tomato[i][j][k] == 0) unripes++; 2. 만약 익지 않은 토마토가 하나도 없다면, 바로 0을 출력하며그렇지 않다면 solution을 진행하여 날짜를 ..
백준 11660 - 구간 합 구하기 5 2024. 10. 6. 문제 : https://www.acmicpc.net/problem/11660 풀이과정NxN 표에서 일정 구간의 합을 구하는 문제이다.(y1, x1)부터 (y2, x2)까지의 합을 구하면 된다. 시간복잡도0. N은 최대 1024이며, 구해야 하는 횟수 M은 최대 100,000 이다.만약 배열을 그대로 입력받아서 100,000번 연산을 하게 되면, 시간복잡도 O(N^2*M) 으로 시간제한 1초 안에 해결할 수 없다. 풀이1. 값을 입력받을때 마다 그 지점까지의 연산 결과를 저장해놓아야 한다.점화식으로 표현하면 아래와 같다.dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + numdp[i][j] 는 table[0][0] ~ table[i][j] 까지의 합 을 의미한다...

티스토리툴바