겜돌이의 개발일지

문제 백준 5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 현재 위치와 이동 횟수를 저장하는 queue를 선언합니다. 위로 올라갈 수 있을 때, 아래로 내려갈 수 있을 때 queue에 push 해주며 bfs를 실행합니다. 현재 위치가 G와 같다면 이동 횟수를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include..

문제 백준 14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 8x8의 작은 배열이기 때문에 가능한 모든 경우의 수에 대해 벽을 만들어 주는 브루트포스 방법을 사용합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 ..

문제 백준 2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 일반적인 dfs, bfs 문제입니다. 저는 bfs로 풀었습니다. 입력을 받고, 사각형이 있는 위치를 1, 없는 위치를 0으로 초기화해줍니다. bfs를 실행하면서 개수와 영역의 넓이를 구합니다. 영역은 vector에 push 해준 뒤, 오름차순으로 정렬하여 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..

문제 백준 22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 풀이 전형적인 bfs, dfs 문제입니다. 투약 전과 투약 후의 상태를 입력받습니다. 루프를 돌면서, 전과 후의 상태가 다르면 그 지점부터 bfs를 해줍니다. bfs 이후에도 전과 후가 다르다면, 백신이 아니므로 NO를 출력합니다. 같다면 YES를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..

문제 백준 11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 1. 각각의 칸을 bfs로 탐색하여 없어지는 칸들을 구합니다. 2-1. 없어지는 칸이 없다면 더 이상 연쇄가 일어나지 않는 것이므로 루프를 종료하고 combo를 출력합니다. 2-2. 없어지는 칸이 있다면 그 칸들을 .으로 바꿔줍니다. 3. 그 후 아래칸부터 접근해 해당칸이 .이고, 그 윗칸이 .이 아닐 경우 당겨줍니다. (중력 적용) 4-1. 당겨지는 칸이 있을 경우에는 3번 과정으로 돌아가 계속 해서 당겨줍니다..

문제 백준 16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 문제 풀이 자체는 직관적인데 구현에 시간이 좀 걸렸습니다. 먼저 먹이를 bfs로 찾아줍니다. (먹이는 상어 크기보다 작아야 하고 상어 크기보다 큰 물고기는 지나갈 수 없습니다!!) 먹을 수 있는 먹이가 있으면, 상어가 이동하는 거리를 계산해 dtarr 배열에 넘깁니다. bfs가 끝나고 먹을 수 있는 먹이가 없으면, 종료하고 cnt를 출력합니다. 먹이가 있다면 가장 짧은 거리, 거리도 같다면 왼쪽 위에 있는 먹이를 목표로 설정합니다..

문제 백준 17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 bfs와 dp를 섞은 듯한 재밌는 문제였습니다. q는 순서대로 현재 파이프 끝의 x좌표 / y좌표 / 상태를 저장합니다. q에다가 push와 pop을 반복하면서, 갈 수 있는 경로의 수를 파악합니다. 각각의 상태에 대해 취할 수 있는 다음 상태를 하드 코딩 했는데, 따로 함수를 만들었다면 더욱 깔끔한 코드가 되었을 것 같습니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

문제 백준 16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 bfs로 나라를 돌면서 인구 수 차가 일정 범위 이내라면 q, checkq에 push 합니다. bfs가 끝난 뒤 checkq에 있는 나라들의 인구를 같게 만들어줍니다. 인구 이동이 발생하지 않을 때 까지 이 과정을 반복하고, 횟수를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..

문제 백준 2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 전형적인 bfs 문제였습니다. 먼저 치즈의 개수를 세주고 temp에 저장합니다. (0,0)은 무조건 공기이므로 bfs를 이용해 공기와 맞닿은 치즈들을 모두 공기로 바꿔줍니다. 다시 치즈의 개수를 세고, 치즈가 없다면 temp와 hour를 출력하고 있다면 bfs를 반복합니다. 소스 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253..