BOJ 20924번: 트리의 기둥과 가지

2021. 8. 16. 01:05· 알고리즘💻/그래프(DFS&BFS)

https://www.acmicpc.net/problem/20924

 

20924번: 트리의 기둥과 가지

첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번

www.acmicpc.net

DFS를 기둥의 길이를 찾는 데 한번, 그리고 가지 길이의 최댓값을 찾는 데 또 한번 총 두 번을 써서 해결할 수 있는 문제였다.

인접리스트를 이용하여 데이터를 받았고, 스택(q)에 탐색노드와 해당 노드까지의 거리를 추가하는 방식으로 풀었다.

처음에 런타임에러(TypeError)가 나서 멘붕이었는데.. 기가노드가 탐색노드인 경우에 해당 노드에 연결된 노드가 2개면 잘못된 값을 출력하는 문제가 있었다. 그래서 해당 경우에 예외처리를 해 주니 통과하였다.

또한 함수 안에서 global 변수를 선언하면 해당 변수의 type이 'function'으로 나와서 max함수로 비교가 되지 않았다. 그래서 함수 내에서 global 변수를 0으로 한번 더 초기화시켜줬다.

import sys
input = sys.stdin.readline
N, R = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, d = map(int, input().split())
    graph[a].append([b,d])
    graph[b].append([a,d])

visit = [False]*(N+1)
q = []
q.append([R,0])
visit[R] = True
column = 0
branch = 0
#기둥까지의 거리
def col():
    global column
    while(q):
        v = q.pop()
        if (len(graph[v[0]])>2):
            q.append([v[0],0])
            break
        for i in graph[v[0]]:
            if (visit[i[0]]==False):
                visit[i[0]] = True
                q.append([i[0],v[1]+i[1]])
    column = v[1]
    
def branch():
    global branch
    branch = 0 #안하면 max에서 오류 발생
    while(q):
        v = q.pop()
        if (len(graph[v[0]])==1):
            branch = max(branch, v[1])
            continue
        for i in graph[v[0]]:
            if (visit[i[0]]==False):
                visit[i[0]] = True
                q.append([i[0],v[1]+i[1]])
if (len(graph[R])==1):                         
    col()
branch()
print(column, branch)
저작자표시 (새창열림)

'알고리즘💻 > 그래프(DFS&BFS)' 카테고리의 다른 글

BOJ 1922번: 네트워크 연결  (0) 2021.08.16
BOJ 22352번: 항체 인식  (0) 2021.08.16
BOJ 14940번: 쉬운 최단거리  (0) 2021.08.14
BOJ 2210번: 숫자판 점프  (0) 2021.08.12
BOJ 9372번: 상근이의 여행  (0) 2021.08.09
'알고리즘💻/그래프(DFS&BFS)' 카테고리의 다른 글
  • BOJ 1922번: 네트워크 연결
  • BOJ 22352번: 항체 인식
  • BOJ 14940번: 쉬운 최단거리
  • BOJ 2210번: 숫자판 점프
호프
호프
호프
Untitled
호프
전체
오늘
어제
  • 분류 전체보기 (341)
    • 오류😬 (4)
    • 스터디📖 (96)
      • 웹 개발 기초 (8)
      • Spring (20)
      • ML, DL (30)
      • Node.js (22)
      • React (0)
      • 블록체인 (12)
      • Go (3)
      • Javascript (1)
    • 알고리즘💻 (153)
      • 그리디 (23)
      • Bruteforce&Backtracking (16)
      • DP (17)
      • 이분탐색&정렬&분할정복 (17)
      • 누적합&투포인터 (6)
      • 스택&큐&덱 (19)
      • 그래프(DFS&BFS) (19)
      • 트리 (7)
      • 우선순위큐&다익스트라 (11)
      • 벨만포드&플로이드와샬 (8)
      • map&set&number theory (5)
      • 기타 (5)
    • 프로젝트 (3)
      • 캡스톤 디자인 프로젝트 (3)
    • 블록체인🔗 (3)
      • Solana (2)
      • 개발 (0)
      • Harmony (1)
    • ASC (6)
    • CS (73)
      • 데이터베이스 (12)
      • 클라우드컴퓨팅 (21)
      • 운영체제 (11)
      • 컴퓨터네트워크 (14)
      • 블록체인응용 (15)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 복습

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
호프
BOJ 20924번: 트리의 기둥과 가지
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.