DFS 혹은 BFS 를 사용하여 풀 수 있는 간단한 문제. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net BFS 를 사용한 풀이 #include #include #include using namespace std; const int MAX = 101; int N, M; int answer=0; vector network[MAX]; bool visited[MAX]; deque Q; int DFS(int v) { Q.push_back(v); visit..

DFS 혹은 BFS로 풀 수 있는 문제다. 비슷한 백준 문제로는 단지번호 붙이기(2667), 토마토(7576)가 있다. https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net BFS/DFS문제에서 좌표에 관련된 문제를 풀이할 때 check point 해당 매트릭스를 저장할 인접 리스트(혹은 인접 행렬)을 선언할 것. 특정 좌표를 기점으로 주변을 탐색하는 문제의 경우 dx,dy 리스트를 선언할 것. 좌표를 저장하는 큐의 경우 자..

DFS를 사용하여 푸는 대표적인 문제중 하나. 순열 문제도 DFS를 사용하여 풀 수 있다는 것에 유의! 문제의 조건에 따라 케이스를 손으로 직접 쓰고, 눈에 보이는 규칙을 정리해서 그대로 코드로 구현하는 과정이 재밌다 :) 더보기 Check Point 1. DFS에서 재귀를 사용할 때의 기본 조건과, 배열 내 데이터를 삽입하고 삭제할때를 유의하여 코드를 구현한다. https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include #include..

DFS와 BFS를 기본적으로 알 수 있었던 문제. BFS의 경우 Queue, DFS의 경우 재귀함수를 사용하여 구현하였다. https://www.acmicpc.net/problem/1260 더보기 Cheak Point 1. BFS 구현 시 Queue에 vertex를 삽입할 때에도 방문 표시를 하는 것을 잊지말자! 2. 각 vertex의 인접 node에 방문할 때 해당 for loop를 해당 vertex의 리스트 사이즈까지 하는 것을 잊지말자! 3. vertex를 방문할 때 두번 방문하지 않도록 bool 타입의 visited를 선언하고, 양방향 그래프의 경우 양쪽 모두 간선을 저장하도록 하자. #include #include #include #include #include #include using nam..

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택 첫 번째(3번..

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participant completion return ["leo", "kiki", "e..