Algorithms/Graph

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에www.acmicpc.net   1. Preview시간 복잡도: O(V+E) 공간 복잡도: O(V or E) 참고 : https://ji-gwang.tistory.com/293 유형: dfs, bfs   2. 초기 접근 방법이분 그래프: 인접한 정점끼리 서로 다른색으로 칠해서 모든 정점을 2가지 색으로만 칠할 수 있는 그래프   2개의 집합을 두고, 인접 노드를 번갈아 저장하는 이상한 방식으로 문제를 접근해 관련 내용 정리는 생..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. Preview 시간 복잡도: O(2N^2) 공간 복잡도: O(2N^2) 참고 : https://hongcoding.tistory.com/18 (최적화) 유형: bfs 2. 초기 접근 방법 1개의 벽을 부술 수 있는 "item"이 있다고 생각하자. 기존의 visited 배열에서는 item 사용 유무를 판단할 수 없으므로 visited[i][j] → visited[i][..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 1. Preview 시간 복잡도: O(N) 공간 복잡도: O(N) 유형: 그래프 탐색, dfs 2. 초기 접근 방법 그래프 탐색을 하면서 자기자신을 만날 때, 즉 사이클이 형성이 되어야 한 팀이다. def dfs(start, x): for k in graph[x]: if not visited[k]: visited[k] = True judge.append(k) dfs(start, k) if visited..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 1. Preview 시간 복잡도: O(6*NM), bfs 공간 복잡도: O(NM) 유형: 그래프 탐색, bfs 2. 초기 접근 방법 visited[e] : 사다리 visited[nx] : 일반 주사위 길 2가지 경우 모두 queue에 삽입하여, 해당 경우를 고려해 탐색하게 된다. for s, e in road: if s == nx and not vis..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 1. Preview 풀이 시간: 35분 + 30분 시간 복잡도: O(NM) 공간 복잡도: O(NM) 2. 초기 접근 방법 board[][] 에서 모두 방문하는데 "dfs 탐색를 진행한 횟수" 라고 생각해 풀었다. 3 4 DLLL DDDU RRRU 곰곰히 고민해보니, 위와 같은 case에서 dfs 탐색이 3번 일어나지만, 필요한 safezone은 1개이다. 3. ..

[초기 접근 방법] '애니팡' 같은 느낌의 문제 4개 이상이 인접한 구역이 있는지를 체크해서 폭탄을 터트린다. 이 때 일단 모든 맵에서 bfs()로 인접 지역을 체크하고 터트릴 폭탄이 있는 경우 터트리고 맵을 내려, 다시 인접한 구역이 있는지 확인한다. [생각] 폭탄이 터트리고, 공백의 칸을 어떻게 내리는지 고민했던 문제 1) 일단 '.'으로 초기화하자 2) 그리고 각 플로우마다 맨 아랫줄부터 . 그리고 그 윗줄에 색깔이 있으면 교환하는 형식으로 내려오는 걸 구현하자 for i in range(11, -1, -1): for j in range(6): if board[i][j] != '.': # 아래에 빈 칸이 있는지 확인하고, 있으면 전부 내려버려 for k in range(11, i, -1): if b..