겜돌이의 개발일지

문제 프로그래머스 132266 부대복귀 C++ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 아주 일반적인 BFS문제. destination(start)부터 BFS를 돌면서, 각각 노드 첫번째 방문시에 얼마나 걸렸는지(cnt)를 배열(dist)에 넣어준다. 방문 전에 배열은 -1로 초기화하고, 처음 방문시에 걸린 횟수(cnt)를 넣어준다. BFS 특성상 가장 첫 방문이 최단 거리이므로 dist값이 -1이 아니라면 이미 방문한 노드이니 갱신해주지 않는다. BFS를 끝내면 sources에 들어있는 노드까지 얼마나 걸리는지를 answer에 넣어준다. 소스..

문제 백준 11725 트리의 부모 찾기 C++ 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 1이 루트기 때문에, 1에서 DFS나 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 #include #include #inc..

문제 백준 13459 구슬 탈출 C++ 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 BFS를 사용한다. 방문 체크를 [빨간색 공 x좌표][빨간색 공 y좌표][파란색 공 x좌표][파란색 공 y좌표]로 4차원 배열을 이용한다. 공을 4방향(위, 아래, 왼쪽, 오른쪽)으로 굴려주면서, 방문하지 않았을 때에만 큐에 넣어주고 도착지점에 도달할 수 있을 때까지 반복한다. 그전에 이미 10번 이상 시도했다면 조건에 부합하지 않으므로 0을 출력한다. 소스 코드 1 2 3..

문제 백준 2665 미로만들기 C++ 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 풀이 두가지 방법으로 풀었다. 첫 번째 방법 1. cnt만큼 벽을 뚫을 수 있게 설정해준다. 2. BFS() 함수를 실행하여 최대 cnt만큼 벽을 뚫으면서 도착지점에 도달할 수 있는지 없는지 확인한다. 3-1. 도착할 수 있다면 true를 return 하고 현재 cnt를 출력한다. 3-2. 도착할 수 없다면 cnt를 1증가시키고 다시 BFS() 함수를 실행한다. 방문 체크를 3차원 배열로 했는데 (y좌표, x좌표, cnt :..

문제 백준 2667 단지번호붙이기 (C++) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 일반적인 BFS / DFS 문제입니다. 이차원배열을 탐색하면서, 방문하지 않았다면 bfs를 시행합니다. 근처에 1인 지역들을 모두 탐색해 cnt로 반환합니다. cnt를 result vector에 넣어주고 정렬합니다. 그 후 result vector의 원소들을 하나씩 출력합니다. 소스 코드 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..

문제 백준 1260 DFS와 BFS (C++) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 탐색의 가장 기본 of 기본 문제입니다. 주어진 조건에 따라 V부터 DFS 및 BFS를 실행하고, node를 출력합니다. 소스 코드 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..

문제 백준 17142 연구소 3 C++ 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 빡구현류의 브루트 포스 + BFS + 시뮬레이션 문제입니다. 1. 바이러스를 M개 만큼 선택한다. (조합 이용) 2. 바이러스를 확산하고 최소 시간을 갱신한다. 소스 코드 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 5..

문제 백준준 1600 말이 되고픈 원숭이 C++ 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 방문을 [y][x][말 이동 사용 횟수]로 체크합니다. bfs를 돌면서, 각각의 지점에서 말 / 원숭이로 이동할 수 있는 지점을 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 4..

문제 백준 1963 소수 경로 C++ 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 1. 에라토스테네스의 체를 사용하여 1 ~ 9999까지 소수 판정을 한다. 1-1. 999 이하의 수는 비밀번호로 허용되지 않으므로 소수가 아니라고 설정한다. 2. bfs로 루프를 돌면서 해당 숫자에서 한 자리만 바꾼 수가 소수인 경우만 Queue에 push 해준다. 3. cnt를 따로 체크해주면서, 변환이 가능하면 cnt를 출력하고 불가능하면 Impossible을 출력한다. 한 자리만 다른 수 만드는 로직을 string을 통해..

문제 백준 13913 숨바꼭질 4 C++ 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 숨바꼭질에서 경로를 저장하는 배열 vector만 추가해주면 될 줄 알았더니 메모리 초과가 떴습니다. 곰곰히 생각해보니 방문하는 모든 지점을 각각의 queue에 저장하는 것이 문제였습니다. 따라서 가장 처음 해당 지점을 방문할 때, 어디서 방문했는지 저장하는 배열을 선언하여 최단 경로만을 저장하는 방식으로 해결하였습니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 ..