GW LABS

쉬운 그래프 문제 중 하나였다. 기본적인 개념을 복습하기 좋게 문제가 설계되어 있었다. 방향 그래프에 대한 개념과 그래프 순회방법을 복습했다. 해당 문제는 인접리스트를 쓸 필요가 없는데 인접 노드가 하나로 고정되어 있기 때문이다. 아래는 소스코드이다. #include #include #include using namespace std; int graph[1001]; bool visited[1001]; void bfs(int start) { queue q; q.push(graph[start]); visited[start] = true; while (!q.empty()) { int now = q.front(); q.pop(); if (!visited[now]) { visited[now] = true; q.p..

한동안 그래프 탐색 문제를 다뤄보지 않아서 복습겸, C++ 공부겸 기본적인 DFS 문제를 풀어봤다. 백준 2644번 촌수계산 문제는 인접 리스트 형태의 자료구조에서 DFS를 통해서 노드의 연결 깊이를 계산하는 문제였다. 인접 리스트이기 때문에 vector를 사용해서 풀었는데 파이썬 보다는 코드가 길어지는 경향이 있다. 아래는 소스코드이다. #include #include #include using namespace std; int search(int searchStart, int searchEnd, vector graph, bool visited[101], int count) { if (searchStart == searchEnd) return count; int answer = -1; visited[s..

백준 2583번 영역 구하기 문제는 그래프 탐색 문제의 응용으로, 주어진 좌표로 탐색할 수 없는 영역을 표시하는 부분을 구현하는 것이 핵심인 문제이다. 처음에 접근할 때에는 좌표의 오른쪽 끝점을 포함해서 표시했는데, 이렇게 구현하면 훨씬 큰 영역을 잡게된다. 오른쪽 끝 점에서 1을 빼주고 영역을 표시하고 DFS로 탐색하면 쉽게 풀 수 있는 문제였다. DFS로 구현했을 때 PyPy3 환경에서는 재귀깊이 초과로 런타임 에러가 발생할 수 있다. Python3 환경에서 실행하자. import sys sys.setrecursionlimit(10**6) def dfs(row, col, table): if table[row][col] == 1: return 1 table[row][col] = 1 dx = [0, 0,..

깊이 우선 탐색을 복습해보면서 재미있는 제약조건을 해결하는 문제였다. 나를 포함한 많은 사람들이 비가 안오는 경우를 놓쳐 정답률이 낮은 것 같다. 깊이 우선 탐색을 하면서 한 번 함수가 종료될 때마다 카운트 변수를 하나씩 늘려주면 조건에 해당하는 영역을 셀 수 있다. import sys sys.setrecursionlimit(10 ** 6) def dfs(row, col, limit_height, table, visited): if visited[row][col]: return dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] visited[row][col] = True for idx in range(4): row_next = row + dy[idx] col_next = col + dx..

그래프와 DFS, 위상정렬을 공부해볼 수 있는 아주 좋은 문제였다. 문제의 조건은 어떤 과목을 수강할 때 선수과목을 먼저 듣고 들어야한다. 주어진 강의 목록들을 모두 수강할 수 있다면 True를, 선수과목에 이상이 있어서 모두 수강할 수 없다면 False를 리턴하면 되는 문제이다. 접근방법은 우선 인접리스트 형태의 그래프를 만들고 깊이 우선 탐색을 하면서 위상정렬을 수행하는 것이다. 탐색 함수가 종료될 때마다 현재 위치를 기록하고, 탐색이 끝났다면 기록한 배열을 뒤집어주면 위상정렬이 수행된다. 위상정렬 배열을 보면서 수강목록들을 다시 보면서 이상이 있다면 False를 리턴하면 해결할 수 있다. from collections import deque class Solution: def canFinish(se..