[프로그래머스] 네트워크 파이썬 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 연결 정보를 따라 a와 b 컴퓨터의 네트워크를 합치자 (union) computers 연결 정보를 완전 탐색하면서 네트워크를 합친다. 이때 computers[a][b] = 1이라면 a와 b 위치가 서로 바뀐 computers[b][a] = 1이다. 이미 computers[a][b]로 컴퓨터a와 컴퓨터b의 네트워크를 합쳤기 때문에 computers[b][a] = 0으로 초기화해서 다음 번..
[백준] 4195번 친구 네트워크 파이썬 풀이
https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 1. 접근 방식 parents는 리스트 대신 딕셔너리를 사용하자. 일반적인 union-find 방식은 리스트의 인덱스를 통해 부모를 탐색하는 작업을 진행했지만, 이 문제에선 인덱스로 부모를 표현할 수 없다. 따라서 딕셔너리 자료형을 사용하여 a의 부모가 누구인지 표현하자. 이때 부모란, a가 속한 네트워크의 대장이라고 생각하면 된다. 어떤 네트워크에 속한 인원 수를 구하기 위해 딕셔너리..
[백준] 1976번 여행 가자 파이썬 풀이
https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 1. 접근 방식 도시 번호가 1부터 N까지이지만, 편의를 위해 0부터 N - 1까지로 변환하자. 도시 정보를 담은 2차원 리스트(maps)의 행과 열의 인덱스는 0부터 N - 1까지이다. 따라서 개발의 편의를 위해 도시 번호를 0부터 시작하게 변경하자. 다만 마지막에 여행 계획이 담긴 도시들의 번호는 문제에서 정한 대로 번호가 1부터 시작하므로, 그 번호에 1을 감소시킨 도시 번호로 연결 정보를 ..
[백준] 1717번 집합의 표현 파이썬 풀이
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 1. 접근 방식 union-find 방식 인덱스를 원소 값으로 갖는, 길이 (n + 1)짜리 리스트를 생성한다. 인덱스가 3이라면, 인덱스 3은 정수, list[3]은 해당 정수가 속한 집합을 의미한다. 따라서 정수 1과 3을 합치고, 정수 4와 5를 합치면 리스트는 위와 같아진다. 이처럼 여러 숫자(노드)가 있고, 두 개의 숫자를 선택하여 두 개가 같은 집합..