hotamul의 개발 이야기

url: https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 핵심 1. 전형적인 시뮬레이션 / 구현 문제 2. 왼쪽 방향 탐색 (반시계 방향 회전) 을 위해 다음과 같이 나머지 연산 사용 int next = robot.dir; // 현재 방향 next에 저장 for (int i =0; i < 4; i++){ // 4 방향 탐색 next = (next + 3) % 4; // 반시계 방향 회전 ... } 3. 중복 탐색을 막기 위해 check ..

url: https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 핵심 1. stack + queue 기능을 할 수 있는 자료 구조 구현 stack의 top 기능을 통해 현재 뱀의 머리를 알 수 있어야 한다. pop 기능은 꼬리를 잘라내야한다 (queue의 pop) 2. 방향을 변경할 때 다음과 같이 나머지 연산을 이용한다. if (DIR[time] != 0) { // 현재 시간에 방향을 변경해야 할 경우 if (DIR[time] == 'L') { // ..

url: https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 핵심 1. 상어가 벽을 만났을 때 방향 전환을 쉽게 하기 위해 dr, dc 배열과 GetReverseDir 함수를 이용한다. const int dr[] = { 0,-1,1,0,0 }; const int dc[] = { 0,0,0,1,-1 }; // 1-->Up, 2--> Down, 3-->Right, 4-->Left int GetReverseDir(int idx)..

url: https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 핵심 1. 공기청정기 행 (row) 위치 robot_r 배열에 저장 2. map 탐색 하며 미세먼지 큐에 저장 (위치 정보 r, c 와 미세먼지 양 map[r][c]를 저장) (처음에는 위치 정보만 저장했으나 미세먼지 확산이 동시에 일어난다고 생각해야 하므로 미세먼지 양도 저장해야 함) 3. bfs와 비슷하게 (추가 push가 없음) 확산 진행 4. 공기청정기의 위, 아래 순환 구..

url: https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 핵심 1. 전형적 dynamic programing 문제 2. map[1001][1001], ans[1001][1001] 생성 3. 점화식 ans[r][c] = map[r][c] + max(map[r-1][c], map[r][c-1], map[r-1][c-1]) 코드 #define _CRT_SECURE_NO_WARNINGS #include int R, C; int ma..

url: https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 핵심 1. 전형적인 시뮬레이션 문제 2. 봄에 나이가 적은 나무 순으로 양분을 먹는 것을 구현하기 위해 deque, sort 사용 (우선순위 큐 사용 시 push 할 때 마다 정렬을 하므로 사용하면 안됨) 코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std;..

url: https://www.acmicpc.net/problem/1600. 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 핵심 1. BFS 활용 2. 벽 부수기 문제와 비슷한 풀이 3. 방문 여부는 check[r 좌표][c 좌표][말 점프 횟수] 4. 말 점프 횟수가 K 이면서 dir (방향 index) 가 4 이상이면 break 5. (R - 1, C - 1) 좌표에 도달하면 거리 return, 모든 탐색을 완료해도 도착지에 다다르지 못할 경우 -1 return 코드 #define ..

url: https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 핵심 1. BFS, DFS 활용 2. 로봇 청소기 위치 ('o'), 쓰레기 위치 ('*') 를 deque에 저장한다. (로봇 청소기의 위치가 가장 맨 앞[0]에 오게 하기 위해) 3. deque저장된 위치들을 배열에 저장 한다 (로봇 청소기 + 쓰레기 수 파악) 4. bfs를 이용해 로봇 청소기와 쓰레기, 각 쓰레기 사이의 최단 거리를 check 배열에 저장한다. 5. dfs를 이용해 최단 ..

url: https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 풀이 핵심 1. BFS 활용 2. 상근이가 외부에서 접근하는 경우, 죄수1&2가 내부에서 나가는 경우 3가지 경우 모두 탐색하여 각각의 벽을 만난 횟수를 기록한다. 3. deque 또는 우선 순위 큐를 이용해 벽일 경우 벽이 아닐 경우를 구분해 큐에 push 한다. (벽을 만나지 않은 경우가 우선적으로 탐색될 수 있도록) 4. 3가지 경우를 모두 합한다. (이 때 벽에서는 중복을 제거해준다) 코드 #..

url: https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 핵심 1. BFS 활용 2. visited 배열을 이용해 중복 방문 방지 3. 목적 층 G 에 도달하지 못하면 -1 return 코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int F, S, G; int df[2]; // df[0] (UP), df[1] (DOWN) int ans; struct elevator..