https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제를 제대로 읽지않아 한참동안 헤매었던 문제였습니다. 턴이 진행되던 중에 말이 4개 이상 쌓이면 게임을 끝내야 하는데 K개와 비교한 것이 문제였습니다. 필요한 배경지식 std::vector 컨테이너에 대한 이해 문제 해결 방법 Vector를 잘 활용하면 직관적으로 풀어낼 수 있습니다. 선언한 변수의 정보는 다음과 같습니다. using pii = pair; using dpi = pair; int ..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 방법 BFS를 이용한 시뮬레이션 구현문제입니다. 모든 인접한 나라와 나라사이에 국경선이 열려있는지, 즉 인접한 나라로 이동할 수 있는지 확인한 다음, 만약 이동할 수 있다면 그 나라를 시작점으로 하여 BFS를 수행하고 인구이동 결과를 업데이트 합니다. 이때 방문처리도 같이 해주어야 합니다. 노드마다 이동할 수 있는지 확인하는 코드가 chkAlly 함수에 구현되어 있고 시작..
백준 21277번 - 짠돌이 호석
https://www.acmicpc.net/problem/21277 21277번: 짠돌이 호석 DIY(Do It Yourself)는 호석이가 제일 좋아하는 컨텐츠이다. 이번 DIY는 동네 친구 하늘이랑 각자 직소 퍼즐을 하나씩 맞춰보기로 했다. 두 개의 퍼즐은 각자 N1 행 M1 열과 N2 행 M2 열의 격자 형태 www.acmicpc.net 문제 해결 방법 어려운 알고리즘을 필요로 하진 않지만 구현이 힘든 문제였습니다. 퍼즐의 최대 크기가 50x50으로 작기 때문에 완전탐색으로도 충분히 풀어낼 수 있습니다. 완전탐색을 위해서 회전된 퍼즐마다 위와 같은 상황들을 모두 비교해야 하는데 그러기 위해선 최대 150*150 크기의 배열이 필요합니다. 여기서 수행시간을 줄이기 위해서는 N,M의 크기마다 정확한 인..
백준 15806번 - 영우의 기숙사 청소
https://www.acmicpc.net/problem/15806 15806번: 영우의 기숙사 청소 통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검 www.acmicpc.net 큐와 간단한 규칙을 이용한 구현문제였습니다. 문제 해결 방법 곰팡이는 1일이 지나면 위와 같이 8개로 증식합니다. 단순한 풀이 방법으로 1일마다 곰팡이 하나하나 8개로 나누어 저장하는 방법을 생각해 봅시다. N이 최대 300이고 t가 최대 10000이므로 최악의 경우 초기 곰팡이가 90000개이고 10000일 후의 결과를 알아야 할때 대충 (90000 * 8 * 10000) 만큼의 수행시간이..
백준 20058번 - 마법사 상어와 파이어스톰
www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 기존의 상어 시리즈와 비슷한 시뮬레이션 문제였습니다. 파이어스톰 시전시 시뮬레이션 과정은 다음과 같습니다. 주어진 L값에 따라 얼음판을 시계방향으로 90도 회전한다. 얼음이 있는 칸마다 인접한 칸중에서 얼음이 있는 칸의 개수가 3개 이상이 아니면 해당칸의 얼음의 양이 1줄어든다. 1번과정을 구현하기 위해 회전하기전 얼음판과 회전후의 얼음판을 비교해보면 얼음판의 회전은 위의 그림에서 초록색 사..
백준 20057번 - 마법사 상어와 토네이도
www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 토네이도가 한칸 이동할때마다 흩날리는 모래를 격자에 업데이트하면서 정해진 범위밖으로 나간 모래의 총량을 계산하는 문제입니다. 구현해야 할 내용은 크게 두가지로 나눠볼 수 있습니다. 토네이도 이동경로 인덱싱 이동 방향에 따른 모래비율 맵핑 우선 토네이도 이동경로 인덱싱은 토네이도 시작점(N/2, N/2)을 기준으로 위치가 바뀌는 방향의 순서가 ← , ↓ , → , ↑ 이고 방향이 ..
www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 아래의 주어진 과정을 그대로 코딩하면 되는 구현문제였습니다. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다. 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다. 파이어볼은 4개의 파이어볼로 나누어진다. 나..
백준 21611번 - 마법사 상어와 블리자드
www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 백준 21610번 - 마법사 상어와 비바라기 백준 21608번 - 상어 초등학교 백준 21609번 - 상어 중학교 새로 올라온 삼성 4문제 중 구현 난이도가 가장 어려운 문제였습니다. M개의 쿼리마다 주어지는 방향(d)과 거리(s)를 이용하여 블리자드 마법 시전시 수행되는 과정은 다음과 같습니다. d방향, 거리가 s이하인 모든 칸의 구슬을 파괴하며 파괴된 칸은 빈 칸이 된다. 구슬이 파괴된 후..