본문 바로가기

algorithm/BOJ

 (63)
백준 7569_토마토(C++) www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net [문제 풀이] BFS를 이용하여 문제를 풀었습니다. 이 문제는 토마토가 아래, 위 옆으로 하루에 한 칸 씩 익어가며 며칠 만에 토마토가 모두 익을 수 있는가를 찾는 문제입니다. 조금 특이하게 3차원 배열을 이용하는 BFS 문제였습니다. 구현 방식은 기본적인 BFS 방식과 유사합니다. 다만 좌표의 옆만 보는 것이 아닌 아래위를 함께 봐야 하는 문제입니다. 코드 설명 배열을 입력받으며 토마토..
백준 2644_촌수계산(C++) www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net [문제 풀이] DFS를 이용하여 문제를 풀었습니다. 이 문제는 주어진 x, y 사이의 관계를 찾는 문제입니다. 이 문제의 경우 DFS와 BFS 모두 사용이 가능합니다. 저는 DFS를 이용하여 문제를 해결했습니다. 코드 설명 2차원 배열 map에 관계를 기록 합니다. map의 x행의 배열에 체크된 i의 자식들을 조사합니다. i가 y 이면 1촌을 반환하고 아닐 경우 i의 자식들을 찾아봅니다. 자식이 ..
백준 2667_단지번호붙이기(C++) www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. www.acmicpc.net [문제 풀이] BFS를 이용하여 문제를 풀었습니다. 이 문제는 연결 된 단지의 총 개수와 집의 개수를 오름차 순으로 정렬하는 문제입니다. 단지의 연결 된 수를 찾는 것이 BFS 방법으로 할 경우 빠르다고 생각하여 BFS를 이용하여 문제를 해결했습니다. 코드 설명 map을 순회하며 1이 있는 지점을 찾습니다. 1이 있는 지점인 경우 BFS 함수를 이용하여 연결 된 집의 개수를 찾습니다. BFS 함수는 다음과 같습니다..
백준 2606_바이러스(C++) www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net [문제 풀이] DFS를 이용하여 문제를 풀었습니다. 이 문제는 전형적이 DFS 문제로 1과 직/간접적으로 연결된 컴퓨터의 개수를 찾는 문제입니다. 1과 연결 된 i의 컴퓨터를 찾고 i와 연결 된 j의 컴퓨터를 찾는 식의 문제로 해결할 수 있습니다. 코드 설명 컴퓨터들의 연결을 2차원 배열에 나타냅니다. 1부터 n까지 반복하며 1과 연결 된 컴퓨터 i를 찾습니다. 1과 연결된 컴퓨터 i가 확인하지 않은 컴퓨터라면 i와..
백준 2178_미로 탐색(C++) www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [문제 풀이] BFS를 이용하여 문제를 풀었습니다. 이 문제는 전형적인 BFS 문제로 시작지점 (0, 0)에서 (n, m)까지 최소 거리를 찾는 문제입니다. 배열의 크기가 최대 100이므로 DFS로 풀게 되면 시간 초과가 나게 됩니다. 코드는 BFS와 DFS 코드 두 개를 게시하겠습니다. BFS 코드 설명 먼저 Queue에 시작지점 (0, 0)과 움직인 횟수 1을 넣습니다. 그 후 네 방향을 보며 갈 수 있는 지역이라면 지역의 좌표와 횟수 +..
백준 6603_로또(C++) www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net [문제 풀이] 조합을 이용하여 문제를 풀었습니다. 이 문제는 숫자 K와 K개의 숫자 집합이 주어졌을 때, 집합의 원소로 이루어져 있는 6개의 숫자를 뽑는 문제였습니다. N개의 숫자에서 C개의 숫자를 뽑는 것이기에 조합을 이용하여 문제를 해결했습니다. 코드 설명 N개의 숫자를 입력받은 후 N - 6 만큼 반복문을 돌면서 6개 번호 중 첫 번째 번호를 정해 줍니다. combination 함수를 이용하여 ..
백준 16395_파스칼의 삼각형(C++) www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net [문제 풀이] 단순 구현을 이용하여 문제를 풀었습니다. 문제에 주어진대로 구현하였으므로 설명은 생략하겠습니다. [코드] #include using namespace std; int n, k, answer = 0; int arr[31][31]; void paskal(int idx) { if(idx) for (int j = 0; j < idx; j++) { if (j == 0) arr[idx][j] =..
백준 1260_DFS와 BFS(C++) www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [문제 풀이] DFS와 BFS를 이용하여 문제를 풀었습니다. 이 문제는 그래프를 구성하는 정점과 간선이 주어질 때 그래프 탐색을 DFS와 BFS로 탐색하는 것을 구현하는 문제입니다. 따라서, DFS와 BFS 함수를 구현하여 주었습니다. DFS 코드 설명 입력으로 주어진 간선을 저장해 둔 map 배열을 N 크기 만큼 돌면서 DFS 함수에 매개변수로 주어진 v 와 연결된 정점을..

티스토리툴바