목록bfs (6)

한량처럼 살고 싶다

[이것이 코딩테스트다]경쟁적 전염(C++)

아래 포스팅에서 상세한 내용을 다루었다! 따라서 이 포스팅에는 소스코드만 올려야징 https://tooyoung.tistory.com/129 [백준]백준 18405번(C++) https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어 tooyoung.tistory.com #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; int N, K; //맵 크기, 바이러스 종류 int** virusMap; ..
PS/이코테 2023. 2. 22. 15:36
[백준]백준 18405번(C++)

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제 해결 과정 바이러스는 숫자가 작은 바이러스부터 전염이 되어야 한다. 따라서 우선순위 큐를 이용하여 큐에 바이러스를 저장할 때마다 그 바이러스의 우선순위가 높으면 자동으로 앞으로 오게 한다. 1초가 지날 때마다 바이러스가 전염되게 하고, 1초가 종료되면 새롭게 전염된 바이러스의 종류와 위치를 큐에 다시 저장한다. -> 이때 전염되는 과정에서 임시 큐에 새롭게 전염..
PS/백준 2023. 2. 22. 15:30
BFS C++로 구현하기

기본 개념 시작 노드를 큐에 넣고 방문처리한다. 큐의 첫번째 노드를 꺼낸다. 꺼낸 노드의 주변 노드 중 방문하지 않은 노드를 전부 큐에 넣고 방문처리한다. 2,3 번 과정을 반복한다. #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; vector graph[9]; bool visited[9] = { false, }; queue q; void input() { graph[1].push_back(2); graph[1].push_back(3); graph[1].push_back(8); graph[2].push_back(1); graph[2].push_back(7); graph[3].push_back(1); graph[..
PS/이코테 2023. 2. 20. 18:13
[이것이 코딩테스트다]미로 탈출(C++)

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=247882118 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. 최근 5년간의 코딩 테스트 기출문제 www.aladin.co.kr 해당 도서의 DFS/BFS 단원의 실전문제 4번 '미로 탈출'을 풀이한다. 01. 이 문제는 DFS가 아니라 왜 BFS로 풀었을까? 시작지점에서 가장 가까운 노드부터 탐색하므로, 최종 도착지까지 가장 가까운 노드만을 타고 들어가게 된다. 따라서 결과에 최단거리가 나오게 된다. 02. 풀이 문제 조건 괴물이 있는 곳은 0, 없..
PS/이코테 2023. 2. 2. 19:15
BFS: Breadth-First Search, 너비 우선 탐색

01. BFS의 정의 ➡️너비 우선 탐색이라고도 부르며, 그래프에서 어떤 노드와 가장 가까운 노드부터 탐색하는 방식이다. ➡️깊이 우선 탐색은 '현 노드보다 더 아래층에 있는 노드'를 방문하는 것이고 너비 우선 탐색은 '현 노드와 같은 층에 있는 노드'를 방문하는 것이다. 그래프가 무엇인지 모르겠다면 아래의 글에서 1번과 2번, 3번을 읽어보고 오자! https://tooyoung.tistory.com/89 DFS: Depth-First Search, 깊이 우선 탐색 01. DFS의 정의와 그래프의 정의 DFS 정의 ➡️깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. ➡️특정한 경로로 탐색하다가 어떤 상황(개발자가 제 tooyoung.tistory.com 02. ..
PS/알고리즘 이론 2023. 2. 2. 16:19
[백준]백준 1697번(C++)

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제가 왜 BFS 문제일까? BFS문제로 풀지 않고 막무가내로 경로를 쫓아가보자. 수빈이가 5에서부터 동생을 찾으러 간다고 가정해보자. 1) 5에서 갈 수 있는 곳은 4, 6, 10 이며 모두 1초가 걸린다. 2) 4, 6, 10에서 각각 갈 수 있는 곳들은 그림 2층에 나와있다 (3 5 8 5 7 12가 나열된 곳) 3) 2층에서 3층으로 갈 수 있는 곳들을 보면 ..
PS/백준 2022. 10. 12. 02:47
이전 Prev 1 Next 다음