겜돌이의 개발일지

문제 프로그래머스 43162 네트워크 C++ 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 풀이 BFS를 사용합니다. 1. 네트워크에 방문해, 인근 네트워크를 모두 방문 처리 해줍니다. 2. N번째 네트워크까지 반복하면서, 그 네트워크를 방문하지 않았다면 1과정을 반복합니다. 3. 총 네트워크의 개수를 return 합니다. 소스 코드 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..

문제 프래그로머스 43165 타겟 넘버 C++ 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 풀이 BFS를 사용했습니다. 첫 숫자의 음수 값, 양수 값을 queue에 push 해주고 queue에서 하나씩 꺼내며 양수를 더한 값, 음수를 더한 값을 다시 queue에 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 30 31 #include..

문제 백준 2573 빙산 C++ 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 일반적인 bfs 문제입니다. 1. melt() 함수로 주변에 바닷물 만큼 빙산의 크기를 감소시켜줍니다. 2. 빙산이 모두 0이 됐다면 0을 출력해줍니다. 3. 빙산이 있다면 (0이 아닌 숫자가 있다면) bfs를 통해 빙산의 개수를 세어줍니다. 4. 빙산의 개수가 2개 이상이라면, 걸린 시간 t를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..

문제 백준 1261 알고스팟 C++ 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 1. 시작점부터 bfs를 실행하여 목적지까지 도달하는 경로를 찾습니다. 2-1. 목적지에 도달하지 못했다면, 이번 bfs를 실행하는 동안 만난 벽(1)들을 빈 방(0)으로 바꿔줍니다. 2-2. 목적지에 도달했다면, 지금까지 실행했던 bfs 횟수 - 1을 출력합니다. 3. 목적지에 도달할 수 있을 때까지 1 ~ 2 과정을 반복합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..

문제 백준 3055 탈출 C++ 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 고슴도치의 위치에서 bfs를 실행합니다. time이 늘어날 때만, 물을 확산해줍니다. 소스 코드 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 66 67 ..

문제 백준 2206 C++ 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 일반적인 BFS 문제였습니다. 다른 문제들과 거의 비슷한데, 벽을 1번까지는 뚫을 수 있으므로 방문체크를 3차원으로 합니다. (x, y, 벽 부순 횟수) 소스 코드 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 4..

문제 백준 2660 회장뽑기 풀이 각 정점마다 bfs를 해준 뒤 깊이를 비교합니다. 깊이가 더 작으면 갱신해주고, 같으면 추가해줍니다. 소스 코드 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 66 67 68 69 70 71 72 73 #include #include #include #include #include using namespace std; vector v[51]; bool visited[51]; int N; i..

문제 백준 6593 상범 빌딩 C++ 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 2차원 배열로 bfs, dfs 문제를 푸는 경우가 많은데 이 문제는 3차원 배열로 풀어야해서 꽤 신선했습니다. 특별할 건 없고, 2차원 배열로 풀던걸 3차원으로 적용시키면 됩니다. 이동할 수 있는 지점은 상 / 하 / 좌 / 우 / 위 / 아래 (동서남북상하)의 6가지 경우입니다. 소스 코드 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 ..

문제 백준 17471 게리맨더링 C++ 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 N까지의 노드를 0과 1로 양분합니다. 0과 1을 양분할 수 있는 모든 경우의 수에 대해 실행합니다. (조합 이용) 0과 1로 양분할 수 있게 영역이 결정되면, 각 영역을 서로 0은 0끼리, 1은 1끼리 연결할 수 있는지 확인힙니다. 연결이 가능하다면, 각각의 합을 구한 후 차를 구하고, 최솟값과 비교하여 갱신합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..

문제 백준 14226 이모티콘 C++ 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 방문 체크를 2차원 배열로 해주는 색다른 문제였습니다. 할 수 있는 행동은 3가지입니다. 1. 화면에 있는 이모티콘 개수만큼 클립보드에 저장하기 2. 클립보드에 있는 이모티콘 개수만큼 화면에 붙여 넣기 3. 화면에 있는 이모티콘 1개 삭제하기 bfs를 돌면서 이모티콘 개수가 일치하지 않을 때 다음 3개에 행동을 모두 queue에 push 해 줍니다. 방문 체크는 [화면 이모티콘 개수][클립보드 이모티콘 개수]로 해줍니다. ..