https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 구현 문제다. 깊게 생각해야 할 부분은 없었고 문제대로 바로 구현했다. 방향이 바뀌는 점을 어떻게 처리해야 하는지 고민이었다. 4방향 좌(1) 하(2) 우(3) 상(4) 으로 나눠서 하나하나 구현했다. 방향이 변해도 흩어지는 비율은 같기 때문에 해당 배열은 한 번만 선언했다. 토네이도는 1칸 (방향전환) 1칸(방향전환) 2칸 (방향전환) 2칸 (방향전환) 3칸 ....
구현
https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 구현 문제다. 나도 내가 뭘 했는지 모르겠다. #include #include #include using namespace std; struct fire { int r; int c; int m; int s; int d; }; vector board[51][51]; vector visit; int v[51][51]; int N, M, K; int main() ..
https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 구현 문제다. 해당 문제는 시간제한이 짧다. 시간제한을 신경써서 최대한 간단하게 작성하려기보단 구현을 먼저하고 시간제한을 신경쓰려고 했다. 한 칸에 여러 나무가 존재할 수 있다는 점이 생각보다 까다로웠다. 나무의 위치를 입력받는 배열로 [100][3]으로 2차원 배열 / [10][10][102]로 3차원 배열 두 가지를 생각했다. 2차원 배열은 각각의 값을 저장하는 것이고, 3차원..
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 덱을 이용한 구현문제다. 스택을 사용해도 될 것 같다고 생각을 했는데 맨 처음 넣은 원소를 확인하기 힘들고 언제 양방향에 넣고 뺄지 모르니까 덱을 사용했다. 헷갈리는 부분이 존재했는데 뱀의 머리를 구하려면 front, 꼬리를 구하려면 back이라고 생각했다. 큐에는 꼬리가 먼저 들어가고 머리가 나중에 추가되는 방식이라 머리가 back, 꼬리가 front였다. 뱀의 머리에 대한 위치를 찾고, 방향에 맞추어..
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net BFS와 구현이 함께 있는 문제다. 문제의 알고리즘 분류를 보니 DFS로도 풀 수 있는 것 같다. 그림 문제처럼 덩어리를 파악하고 치즈 문제처럼 배열 전체에 BFS를 적용하는 횟수를 구해야 한다고 생각했다. 경험이 있는 문제들의 응용 문제 같아서 알고리즘이 쉽게 떠올랐다. 이 문제의 주의점은 올해(?) 녹은 빙산이 0이 되어 다른 빙산에 영향을 주면 안된다는 것이다. 이걸 해결하기 위해서는 ..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net BFS와 구현이 함께 있는 문제다. 인접한 국가의 인원수가 조건을 만족하면 하나의 영역으로 묶되, 그 국가들을 모두 기록해둬야 한다는 점이 복잡하게 만들었다. 효율적인 방법을 찾다가 그냥 큐 하나를 더 만들었다...^^ 인접한 국가 덩어리를 모두 찾은 뒤 해당 국가들의 인원 수를 변경해주는 작업을 계속해줘야 해서 반복문을 많이 이용했다. 더 이상 국경선이 열리지 않을때까지 반복하고 ..
