hotamul의 개발 이야기

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..

url: https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 핵심 1. BFS 활용 가장 가까운 물고기를 먹으러 간다 2. 우선 순위 큐 활용 (algorithm 헤더의 sort() 함수를 이용) 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 거리가 가장 가까..

url: https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 풀이 핵심 1. bool type의 방문 여부 확인 용 3차원 배열 2. queue 최대 크기 (1000 * 1000 * 10) 3. 다음 탐색 위치가 벽이면서 현재 벽을 부순 횟수가 K보다 작다면 다음과 같이 큐에 추가 if (map[nr][nc]) { if (cur.wall < K) { visited[nr][nc][cur.wall] = visited..

url: https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 풀이 핵심 1. 방문 여부 체크 하지 않는다 (중복 해서 방문 할 수 있으므로) 2. 다음 2가지 조건 중 하나라도 만족하면 가장 오른쪽 윗 칸에 도달할 수 있다고 판단한다 현재 위치가 가장 오른쪽 윗 칸이라면 남아있는 벽이 없다면 코드 #define _CRT_SECURE_NO_WARNINGS #include #define N (8) int sr = 7, sc = 0, er =..