겜돌이의 개발일지

문제 백준 1937 욕심쟁이 판다 C++ 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 dp와 dfs가 섞인 재밌는 문제이다. dp 배열은 해당 칸에서 판다가 시작할 시에, 먹을 수 있는 최대 대나무를 가지고 있는 배열이다. (-1로 초기화) dfs를 돌면서 다음과 같은 과정을 거친다. 1. 어느 곳에서 시작하든, 자기 자신 칸에 있는 대나무는 먹을 수 있다. 따라서 dp 배열의 최소값은 1이다. result 값을 먼저 1로 설정한다. 2. 상하좌우 순으로, 다음값이 현재값보다 크다면 둘 중..

문제 백준 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..

문제 백준 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..

문제 프래그로머스 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..

문제 백준 1967 트리의 지름 C++ 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 dfs를 사용합니다. 1. 1이 항상 루트 노드이므로, 1에서 가장 먼 노드를 찾습니다. 2. 가장 먼 노드에서 다시 dfs를 실행하여, 다른 가장 먼 노드 까지의 거리를 구합니다. 3. 그 거리가 트리의 지름이 됩니다. 트리의 지름을 출력합니다. 소스 코드 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..

문제 백준 1987 C++ 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 0, 0 지점부터 DFS를 실행하여 최대 깊이를 구해줍니다. 해당 지점을 방문했는지를 저장하는 mapvisited 배열과 해당 문자열을 방문했는지를 저장하는 charvisited 배열을 모두 사용하여 방문 체크를 합니다. 소스 코드 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 ..

문제 백준 13023 ABCDE C++ 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 깊이가 4이상인 노드가 있는지 확인하는 문제입니다. 각각의 노드에서 DFS를 실행하여 깊이가 4가 이상이 되는지 확인합니다. 소스 코드 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 #include #include using namespace std; vector v[2000]; bool visited[2000]; bool ispossible; void ..

문제 백준 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 ..