24480번: 알고리즘 수업 - 깊이 우선 탐색 2

24480번:  알고리즘 수업 - 깊이 우선 탐색 2사용 언어: C++ 풀이24479번과 동일한 풀이이지만 sort만 내림차순으로 한다.sort 함수에 greater을 넣어줘서 앞에 수가 뒤에 수보다 크면 true 리턴해서 내림차순으로 sort 된다.#include #include #include using namespace std;vector graph[100001];bool visited[100001];int order[100001];int cnt = 1;void dfs(int node){ visited[node] = true; order[node] = cnt++; sort(graph[node].begin(), graph[node].end(), greater()); for (in..

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

24479번:  알고리즘 수업 - 깊이 우선 탐색 1사용 언어: C++ 풀이무방향 그래프이므로 양쪽 인덱스에 넣어주고, 시작 노드부터 dfs를 돌린다.dfs에서는 visited를 true로 해주고, 방문한 노드의 순서를 order로 저장하고, 오름차순 방문이므로 sort를 하고 다음 인접 노드가 방문하지 않은 노드면 재귀를 돌린다.#include #include #include using namespace std;vector graph[100001]; bool visited[100001]; int order[100001]; int cnt = 1; void dfs(int node) { visited[node] = true; order[nod..

1012번: 유기농 배추 (BOJ C/C++)

1012번: 유기농 배추 사용 언어: C 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으..

2606번: 바이러스 (BOJ C/C++)

2606번: 바이러스 사용 언어: C 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 ..

2667번: 단지번호붙이기

2667번: 단지번호붙이기(BOJ C/C++) 사용 언어: C 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된..

1260번: DFS와 BFS

1260번: DFS와 BFS(BOJ C/C++) 사용 언어: C 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한..

DFS, BFS (인접 행렬로 구현)

DFS 기본 설명 DFS (Depth First Search, 깊이 우선 탐색) DFS의 특징을 설명하자면 탐색을 한 방향으로 시작하면 갈 수 있는 최대한 깊게 간다. 그래서 위의 그래프를 예시로 하면 우선은 정점 1->2->4 들을 먼저 탐색할 것이다. 이다음으로는, 4에서 길이 막혔으므로 정점 2, 1로 되돌아가면서 다른 방향으로 탐색할 수 있는지 확인을 한다. 2에서는 다른 곳으로 갈 수 없고, 1에서 3 쪽으로 갈 수 있으므로 1->3->5 순으로 탐색을 할 것이다. 그리고 또 정점 3으로 돌아오면 6으로 갈 수 있으므로 6까지 탐색을 한다. 그러면 길이 또 막혔으므로 정점 3, 1 순으로 되돌아오면 더 이상 탐색할 수 있는 곳이 없으므로 탐색이 끝나는 것이다. 결과를 종합해보면 1->2->4->..