ji_iin
iOSLog
ji_iin
전체 방문자
오늘
어제
  • 분류 전체보기 (56)
    • Swift (8)
    • iOS (6)
    • 알고리즘 (34)
    • CS (3)
    • 회고 (3)
    • 제품리뷰 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 백준
  • Python
  • SWiFT
  • 2022년 회고
  • Bye2023
  • 개발회고
  • 너비우선탐색
  • ios
  • 다이나믹 프로그래밍
  • 그래프탐색
  • 자바
  • 알고리즘개념
  • 그래프이론
  • 재귀
  • opional
  • django
  • 깊이우선탐색
  • 회고
  • swiftUI
  • 대기업코테
  • 구조체와 클래스
  • 알고리즘
  • 수학
  • 공식문서
  • 정렬
  • 백트래킹
  • 파이썬
  • 프로그래머스
  • 깊은복사와 얕은복사
  • 브루트포스 알고리즘

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
ji_iin
알고리즘

[Python] 백준 5567번 : 결혼식

알고리즘

[Python] 백준 5567번 : 결혼식

2021. 9. 6. 14:38

문제

5567번: 결혼식

[ 문제 조건 ]

  • n : 동기의 수 (즉, 숫자의 종류)
  • m : 친구 관계 나타내는 리스트 개수

[ 해결순서 ]

  1. 상근이는 결혼식에 자신의 친구 + 친구의 친구까지 초대 가능하므로 너비우선탐색을 이용해서
  2. 자신의 친구먼저 몇명인지 탐색 후 친구의 친구까지 탐색한다.
  3. bfs 메소드를 이용해서 친구 1명을 먼저 구한다음
  4. 그 친구의 친구까지 탐색하고 다음 친구의 친구의 친구 탐색하고 초대인원 값 + 1하면
  5. 깊이를 계산해서 깊이가 2이면 (친구의 친구까지만 초대가능하므로) 총 초대인원 출력하고 종료한다.

✏️한줄평

: 처음에 이진트리를 생각해서 그렇게 풀려고 했는데 사실 굳이 그럴필요 없이 그냥 bfs로 친구들 탐색하고 깊이 +1 하다보면 구해지는 문제였다.


코드

from collections import deque
def bfs(start):
dq = deque()
dq.append(start)
visited[start] = True #1은 방문처리
count = 0 #초대할 사람이 몇 명인지
depth = 0 #깊이가 2이면 끝
while dq:
depth += 1
for _ in range(len(dq)):
friend = dq.popleft()
for val in list[friend]:
if not(visited[val]):
visited[val] = True
dq.append(val)
count += 1
if depth == 2:
print(count)
break
n = int(input())
m = int(input())
list = [[] for _ in range(n+1)] #n명의 친구관계를 나타내야 함
visited = [False] * (n+1)
#양방향 그래프로 연결
for _ in range(m):
a, b = map(int,input().split())
list[a].append(b)
list[b].append(a)
bfs(1)
view raw BOJ5567.py hosted with ❤ by GitHub

'알고리즘' 카테고리의 다른 글

[Python] 백준 15992번 : 1, 2, 3 더하기 7  (0) 2021.09.13
[Python] 카카오 2021 BLIND : 신규 아이디 추천  (0) 2021.09.13
[Python] 백준 14888번 : 연산자 끼워넣기  (0) 2021.09.06
[Python] 백준 1074번 : Z  (0) 2021.08.30
[Python] 백준 11051 : 이항 계수 2  (0) 2021.08.29
  • 문제
  • [ 문제 조건 ]
  • [ 해결순서 ]
  • ✏️한줄평
  • 코드
'알고리즘' 카테고리의 다른 글
  • [Python] 백준 15992번 : 1, 2, 3 더하기 7
  • [Python] 카카오 2021 BLIND : 신규 아이디 추천
  • [Python] 백준 14888번 : 연산자 끼워넣기
  • [Python] 백준 1074번 : Z
ji_iin
ji_iin
개발성장일지🐥

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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