본문 바로가기

dfs

(2)
백준 22239 가희와 읽기 쓰기 놀이2(python) 문제 https://www.acmicpc.net/problem/22239 22239번: 가희와 읽기 쓰기 놀이 2 결과 리스트가 [2, 1, 2, 2, 3, 4, 2, 3]으로 주어졌다고 생각해 보겠습니다. [그림 1] 유효한 결과 리스트 결과 리스트에서 두 번 이상 등장한 수는 2, 3입니다. 2가 등장한 횟수는 4번, 3이 등장한 횟수 www.acmicpc.net 구현하기 까다로웠던 문제였습니다. DFS 방식으로 접근하여 풀었습니다. 주어진 제약 조건에 맞게 카드와 사람들 간에 관계를 연결하여 푸는 문제였습니다. 과정은 다음과 같습니다. 주어진 제약들과 카드 값들을 입력받고, 제약에 맞게 카드값들에 플레이어 번호를 넣어 줍니다. 탐색하는 함수에서는 만들어내야하는 결괏값이 있는지 확인하고, 있다면 값을..
백준 2617 구슬 찾기(python) 문제 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 그래프 탐색으로 접근할 수 있는 문제입니다. DFS, BFS 어떤 것을 사용해도 무방하지만 저는 플로이드-워샬이 먼저 떠올랐기 때문에 이 방식으로 풀어보았습니다. 출력해야 되는 값이 무게가 절대로 중간값이 될 수 없는 구슬의 개수를 세는 문제였습니다. 풀이 과정은 다음과 같습니다. 먼저 입력으로 들어오는 구슬 번호대로 무게 순서를 지켜 관계를 2차원 리스트에 1로 표시해 줍..