o_onn5

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소스패닝 트리를 만드는 크루스칼 문제다. 전형적인 크루스칼 문제라서 개념을 아는 사람이라면 쉽게 풀 수 있다. import math # 특정 원소가 속한 집합 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) ret..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 전체적인 로직은 다른 사람들도 쉽게 잡았을거라고 생각한다. 그래서 쉽게 풀 수 있을 것이라 생각했는데 풀고 제출하니 시간초과;; 알고리즘은 다음과 같다 0. 벽으로 둘러싸인 빈 공간을 하나의 구역으로 취급한다. 1. BFS를 통해 각 구역의 빈 칸 개수를 따로 저장한다. (난 area 딕셔너리에 저장했다.) 2. 방문 처리를 위한 visited에는 구역의 번호를 저장한다. 3..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 구슬이 겹쳤을 때가 관건인 문제였다.(이거 고민하느라 오래걸려서...) BFS는 둘째치고 시뮬레이션 너무 복잡한 것 같다. 삼성 SW 역량 테스트 문제라는데ㅋㅋㅋㅋ... 어려웠다ㅜ from collections import deque n,m = map(int,input().split()) board = [list(map(str, input())) ..