Algorithm/Graph13 [백준] 2638번 치즈 _ Python 보호되어 있는 글 입니다. 2024. 4. 16. [백준] 13549번 숨바꼭질 3 _ Python 보호되어 있는 글 입니다. 2024. 4. 14. [백준] 1707번 이분 그래프 _ Python 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개의 집합을 두고, 인접 노드를 번갈아 저장하는 이상한 방식으로 문제를 접근해 관련 내용 정리는 생략.. 2024. 4. 10. [백준] 2206번 벽 부수고 이동하기 _ Python 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][.. 2024. 4. 9. [백준] 9466번 텀 프로젝트 _ Python 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.. 2024. 3. 20. [백준] 16928번 뱀과 사다리 게임 _ Python 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.. 2024. 3. 17. 이전 1 2 3 다음
