0. 문제'''부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다.예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로나와 할아버지는 2촌이 되고,아버지 형제들과 할아버지는 1촌,나와 아버지 형제들과는 3촌이 된다.여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다.입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고,둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다.그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다.넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나..
0. 문제'''정사각형 모양의 지도가 있다.1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다.여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.대각선상에 집이 있는 경우는 연결된 것이 아니다.지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고,그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.첫 번째 줄에는 총 단지수를 출력하시오.그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오..
0. 문제 및 입력값'''신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다.한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다.컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때,1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.1. 컴퓨터의 수 (100 이하인 양의 정수)- 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.2. 컴퓨터 쌍의 수3. 한 줄에 한 쌍씩, 컴퓨터의 번호 쌍1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.''''''761 22 31 55 25 64 7# 4''' 1. 제출..
0. 문제'''N×M크기의 배열로 표현되는 미로가 있다.미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.이러한 미로가 주어졌을 때,(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.다음 N개의 줄에는 M개의 정수로 미로가 주어진다.각각의 수들은 붙어서 입력으로 주어진다.첫째 줄에 지나야 하는 최소의 칸 수를 출력한다.항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.''''''4 610111110101010101..
0. 문제'''그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,더 이상 방문할 수 있는 점이 없는 경우 종료한다.정점 번호는 1번부터 N번까지이다.# 입력첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다.다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.# 출력첫째 줄에 DFS를 수행한 결과를,그 다음 줄에는 BFS를 수행한 결과를 출력한다.V부터 방문된 점을 순서대로 출력하면 된다.'''..
대표 문제 유형1. 경로탐색 유형 (최단거리, 시간)2. 네트워크 유형 (연결)3. 조합 유형 (모든 조합 만들기) DFSBFS알고리즘 검증동작 검증을 하기 쉬움어려움 코드 간결, 버그 발생할 가능성 적음 수행 시간복불복대박날 확률도 적지만 쪽박 찰 확율도 적다= 시간 복잡도높다낮다문제 난이도쉬운 문제일 경우 추천난이도 있어보이거나 DFS로 풀기 오래걸릴 것 같은 경우 추천 => 한 문제를 두 방식으로 풀어보며 익혀두기 백준 연습 문제1260 -- DFS와 BFS : 그래프에서 DFS / BFS 연습2606 -- 바이러스 : 그래프에서 DFS 활용 연습2667 -- 단지번호붙이기 : DFS를 이용한 Flood Fill 연습2178 -- 미로탐색 : BFS로 4방향 탐색 연습7569 -- 토마토 : B..
DFS/BFS 는 대표적인 탐색 알고리즘이다.탐색이란, 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다루기 때문에기본 자료구조인 스택과 큐에 대해 제대로 이해하고 있어야 한다. 자료구조란, 데이터를 표현하고 관리하고 처리하기 위한 구조이다. 스택과 큐의 자료구조는 삽입(Push), 삭제(Pop), 오버플로, 언더플로 등을 고려해야 한다.** 오버플로 - 수용 크기가 가득 찬 상태에서 삽입 연산 수행시 발생** 언더플로 - 데이터가 전혀 없는 상태에서 삭제 연산 수행시 발생 1. 스택 (Stack)- 선입후출, 후입선출 (ex. 박스 쌓기) stack = []stack.append(5)stack.append(2)stack.append(..
