본문 바로가기
728x90

dfs4

BOJ - 1926번, 그림 문제 DFS를 이용한 풀이 이번 문제는 DFS 태그가 걸려있는 문제를 찾다가, 풀게된 1926번 문제 정리입니다. 문제 자체는 전형적인 DFS로 해결할 수 있는 간단한 문제였는데, 잘못 생각한 부분들이 있어 오답 처리를 받게된 부분을 정리해보려고 합니다. 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로.. 2022. 12. 29.
백준 - 5014번, 스타트링크 문제, BFS 방식 풀이 정리 (C++) 이번에 풀이한 문제는? 백준 5014번 스타트링크 문제 풀이 정리입니다. https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net solved.ac 기준 실버 1 난이도의 문제이고 저는 BFS 방식으로 그래프를 탐색하는 알고리즘을 적용해서 풀이해 봤습니다. 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 .. 2022. 11. 9.
이분 그래프 (Bipartite Graph) 정리 이분 그래프(Bipartite Graph) 란? 이분 그래프(Bipartite Graph)는 그래프의 정점을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 의미한다고 합니다. 제가 풀이한 백준 1707번 이분 그래프 문제에서는 설명하고 있어 무슨 말인가 싶어 구글링을 통해 찾아본 결과 이분 그래프는 인접한 정점끼리 서로 다른 색으로 칠했을 때 모든 정점을 두 가지의 색으로 칠할 수 있는 그래프이다! 이러한 성질로 인해서 같은 그룹의 정점끼리는 간선으로 연결되지 않고, 간선은 서로 다른 그룹에 대한 정점만을 연결하는 특징을 갖습니다. 참고로 간선 없이 하나의 정점으로 존재하는 그래프 또한 이분 그래프(Bipartite graph)라고 할 수 있습니다! 이분 그래프.. 2022. 9. 17.
BOJ - 1388번 바닥 장식, DFS를 이용한 풀이 이번에는 대표적인 그래프 탐색 알고리즘 중 하나인, DFS를 이용해 1388번 바닥 장식 문제를 푼 과정을 정리해 보려고 합니다. 우선 문제 링크는 다음과 같습니다. 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 풀이에 들어가기 앞서 혹시 그래프 탐색 알고리즘인 DFS, BFS에 대한 개념 이해가 부족한 분들은 아래의 글을 참고해도 좋을 것 같습니다! [알고리즘] DFS(Depth First Search), 깊이 우선 탐색 방식 정리 순서 그래프란? DFS(Depth First Search)에 대해서 DFS를 구현.. 2022. 7. 22.
728x90

티스토리툴바