# DFS

91개의 포스트
post-thumbnail

백준 14502번: 연구소

문제인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나

약 13시간 전
·
0개의 댓글

알고리즘 문제 해결 전략 28.7 정리1

1\. 깊이 우선 탐색과 간선의 분류깊이 우선 탐색(DFS)을 수행하면 일부 간선은 처음 발견한 정점에 연결돼 있어서 채택을 하고 나머지는 무시하게 된다. 하지만 무시되는 간선들에 관심을 가지면 유용한 정보를 얻을 수 있다. 어떤 그래프를 깊이 우선 탐색했을 때, 탐색

5일 전
·
0개의 댓글
post-thumbnail

[BOJ] 효율적인 해킹 #1325

https://www.acmicpc.net/problem/1325난이도: 하문제 유형: DFS, BFS그래프 기본 탐색: 핵심 유형 문제풀이해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에

6일 전
·
0개의 댓글
post-thumbnail

백준 2667번: 단지번호붙이기

문제<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른

2020년 8월 4일
·
0개의 댓글
post-thumbnail

[BOJ] 유기농 배추 #1012

https://www.acmicpc.net/problem/1012난이도: 하문제 유형: DFS, BFS출제 빈도: 매우 높음그래프 기본 탐색차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충

2020년 8월 4일
·
0개의 댓글
post-thumbnail

[BOJ] 바이러스 #2606

https://www.acmicpc.net/problem/2606난이도: 하문제 유형: DFS, BFS그래프 기본 탐색신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴

2020년 8월 4일
·
0개의 댓글
post-thumbnail

[BOJ] DFS와 BFS #1260

https://www.acmicpc.net/problem/1260알고리즘: 그래프 기본 탐색그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문

2020년 8월 3일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 경로찾기

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다.

2020년 7월 30일
·
0개의 댓글
post-thumbnail

알고리즘 :: 백준 :: DFS :: 4963 :: 섬의 개수

전형적인 DFS의 그래프 세그먼트 개수 구하기 문제다.모든 정점에 대해 DFS를 수행한 뒤 DFS가 종료됨은 각 세그먼트에 대해 탐색이 끝났음을 의미하므로 카운팅해주면 전체 섬의 개수를 구할 수 있다.vector<bool> 사용을 지양하고 bitset또는 일반 b

2020년 7월 26일
·
0개의 댓글
post-thumbnail

알고리즘 :: 알고스팟 :: DFS :: WORDCHAIN (끝말잇기)

https://algospot.com/judge/problem/read/WORDCHAIN두 가지 전략이 존재한다.각 단어(문자열)를 정점으로 하는 그래프를 만든다.끝말잇기가 성립하기 위해서는 모든 정점을 1회씩 탐방할 수 있어야 한다.각 단어(문자열)의 첫문자

2020년 7월 24일
·
0개의 댓글
post-thumbnail

알고리즘 :: 알고스팟 :: DFS :: DICTIONARY (고대어 사전)

링크: https://algospot.com/judge/problem/read/DICTIONARY종만북 DFS 파트의 난도 '하'로 제시된 문제이나 아직 DFS와 위상정렬(topological sort)에 대해 익숙하지 않아서 상당히 어렵게 느껴진 문제였다.

2020년 7월 24일
·
0개의 댓글

[programmers] 타겟 넘버

see also : https://programmers.co.kr/learn/courses/30/lessons/43165?language=javascriptfor문을 이용해 모든 경우를 다 탐색한다면 시간초과가 날 것으로 보인다. 이런 종류의 bfs, dfs는

2020년 7월 24일
·
0개의 댓글
post-thumbnail

알고리즘 :: 백준 :: DFS :: 6603 :: 로또

로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법

2020년 7월 22일
·
0개의 댓글
post-thumbnail

DFS와 BFS

그래프 이론을 통해서 그래프에서 사용되어지는 용어들을 알아봤다. 이제 모든 자료구조의 기초가 되는 탐색 연산을 알아볼 차례인데, DFS와 BFS로 두가지 연산이 존재한다.깊이 우선 탐색(Depth-First-Search)는 너비 우선 탐색과 달리 탐색 방향이 아래로 진

2020년 7월 20일
·
0개의 댓글

프로그래머스 알고리즘

해결 문항https://programmers.co.kr/learn/courses/30/lessons/43165https://programmers.co.kr/learn/courses/30/lessons/43162도전 중인 문항https://pr

2020년 7월 19일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집

2020년 7월 16일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.첫째 줄

2020년 7월 14일
·
2개의 댓글

프로그래머스 불량 사용자 (카카오 2019 인턴 3번)

카카오 2019년도 겨울 인턴 문제 중 하나인 불량 사용자를 풀어보도록 하겠습니다.효율성을 위한 다양한 풀이 방법이 있을텐데요, 정규식이나 비트마스킹 등을 사용하지 않고 풀어보도록 하겠습니다.https://programmers.co.kr/learn/course

2020년 6월 27일
·
0개의 댓글
post-thumbnail

[TIL] 2020. 06. 26. DFS_BFS

하나의 버텍스(Vertex)으로부터 시작하여 모든 정점들을 순회하는 것.그래프(Graph) 탐색의 종류에는 DFS(Depth First Search)와 BFS(Breadth First Search)가 있다.트리(Tree) 자료구조는 방향성 있는 그래프이므로, DFS와

2020년 6월 26일
·
0개의 댓글