jungle python 백준 11725 2617 2644 algorithm

파이썬 알고리즘 3주차 : 촌수계산, 트리의 부모 찾기, 구슬 찾기

정글일지 15

1.개발 진행 및 완료상황

  • 2주차 python algorithm dfs 문제 1회독 완료
  • CSAPP 2주차 목표 읽기

  • 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용

  • 백준 2644(파이썬)

2644번: 촌수계산

문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력 사람들은 1, 2…

www.acmicpc.net

풀이 과정 : 부모 자식간이 1촌이라는 것을 기준으로 계산할 수 있다. 즉 DFS과정에서 재귀 깊이때마다 cnt값을 +1 해주면 도달 후 cnt값을 통해 촌수를 알 수 있다.

정답 코드:

import sys n = int(sys.stdin.readline()) start, end = map(int,sys.stdin.readline().split()) m = int(sys.stdin.readline()) graph = [[] for _ in range(n+1)] for _ in range(m): parent,son = map(int,sys.stdin.readline().split()) graph[parent].append(son) graph[son].append(parent) ans = [] visited = [False]*(n+1) def dfs(start,cnt): cnt += 1 visited[start] = True if start==end: ans.append(cnt) for i in graph[start]: if not visited[i]: dfs(i,cnt) dfs(start,0) if len(ans) == 0: print(-1) else: print(ans[0]-1)

  • 백준 11725(파이썬)

11725번: 트리의 부모 찾기

11725번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 트리의 부모 찾기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 56984 25071 17817 42.231% 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모…

www.acmicpc.net

풀이 과정: 보통 이미 방문한 노드는 True/False나 0/1로 표시하였는데, 이번 문제에서는 다음 목적지 노드를 index로 하는 visited 원소의 원소값을 현재 위치해있는 노드의 값을 부여하였다. 이러한 방식으로 각 노드의 부모노드를 찾을 수 있었다.

정답코드

import sys sys.setrecursionlimit(10*6) n = int(sys.stdin.readline()) graph = [[] for i in range(n+1)] for i in range(n-1): a, b = map(int, sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a) visited = [0](n+1) def dfs(s): for i in graph[s]: if visited[i] == 0: visited[i] = s dfs(i) dfs(1) for x in range(2, n+1): print(visited[x])

  • 백준 2617(파이썬)

2617번: 구슬 찾기

2617번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 구슬 찾기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 7616 2449 1806 32.670% 문제 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,…,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다. 우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려…

www.acmicpc.net

풀이 과정 : 우선 각 노드를 따라 dfs를 통해 총 이동한 노드 갯수와 (n+1)/2의 비교를 통해서 풀고자 하였다. 하지만 양 방향으로 설정해서 그런지 정확한 값이 나오지 않았다. 실패한 이후 평소 그래프 설정과 다르게 무거운 공 -> 가벼운 공 이동만 포함하고, 그 반대도 따로 설정했다. 하지만 정확한 값이 나오지 않아 오답처리 됐다.

공부한 방법은 다음과 같다. 특정 노드의 하부 트리에 속하는 노드 숫자를 DFS를 통해 구하는 방식이였다. 무게가 무거운 구슬 그룹과 가벼운 구슬 구릅으로 나눈 뒤 루트가 더 큰 그래프, 작은 그래프 구조로 또 나누어 탐색하였다. 선택한 노드보다 무거운 구슬 갯수 혹은 가벼운 구슬 갯수가 (n+1)/2를 넘으면 중간값이 될 수 없는 노드이다.

정답 코드

#DFS with recursion import sys from collections import deque input=sys.stdin.readline N, M =map(int,input().split()) biggerlst=[[] for * in range(N+1)] # index보다 큰 수 smallerlst=[[] for * in range(N+1)] # index보다 작은 수 mid=(N+1)/2 #개수 기준 중간값 for i in range(M): #값 입력후 배열 a,b=map(int,input().split()) bigger_lst[b].append(a) smaller_lst[a].append(b) def dfs(arr, n): #bigger, smaller, list보고 n보다 크거나 작은 숫자 개수 파악 global cnt for i in arr[n]: if not visited[i]: visited[i]=True cnt+=1 dfs(arr,i) answer=0 for i in range(1,N+1): visited=[False]*(N+1) cnt=0 dfs(bigger_lst,i) if cnt>=mid: answer+=1 cnt=0 dfs(smaller_lst,i) if cnt>=mid: answer+=1 print(answer)

  1. 새로 배운 내용
  • dfs는 두 가지 방법이 있다. 각각 스택, 재귀함수를 이용하는 것이다. 우선은 재귀함수를 이용하는 방법만 공부하고 있지만 스택도 이용할 줄 알아야 겠다.
  1. 참고할 만한 레퍼런스들
  • 자료구조와 함께 배우는 알고리즘 입문 파이썬편(BohYoh Shibata 지음, 강민 옮김, 이지스 퍼블리싱)
  • https://wonyoung2257.tistory.com/56
  • https://d-cron.tistory.com/22
  • https://conak-diary.tistory.com/89
  • https://campkim.tistory.com/17

  • 특이사항

  • 일요일이긴 하지만 쉴 여유가 없다.

  • 회고

  • dfs 코드의 구성에 대해 열심히 공부하니 어려운 문제더라도 접근은 가능하다. 비록 어떻게 원하는 결과를 추출해낼지는 여전히 어렵지만.. 또한 재귀 깊이나 시간복잡도를 고려하는 건 여전히 힘들었다.
  • TO-DO-LIST
  1. 3주차 파이썬 알고리즘 DFS 복습
  2. 3주차 파이썬 알고리즘 BFS 문제 풀이
CATALOG
    log