문제 주소 : https://www.acmicpc.net/problem/9466
디브리핑
- 문제풀이 시간
[] 20분 내로 풀이 완료
[] 40분 내로 풀이 완료
[] 1시간 내로 풀이 완료
[] 2시간 내로 풀이 완료
[] 풀이 실패
- 부족한 부분
[] 구현력
[] 문제해결능력
[] 배경지식
[문제설명]
이 문제는 간단하게 보자면 연결된 그래프가 몇개가 만들어지는가에 관한 문제이다.
문제의 조건으로
- 첫재줄에는 테스트 케이스의 갯수 T
- 둘째 줄에는 학생의 수 (2 <= n <= 100,000)
- 셋째 줄에는 선택된 학생들의 번호( 1 < number < 100,00)
- 이후로는 2,3 반복
이렇게 주어진다.
[의사코드]
처음 접근 방식은 학생들의 수 만큼의 선택된 학생들의 번호 리스트와 visited 리스트를 만든 후 처음 학생부터 끝까지 학생의 인덱스만큼 순회하여 해당 학생이 선택한 학생의 번호가 하나의 연결된 그래프가 형성되는지 알아보는 식을 구상하였으나 어떻게 구현해야할지 잘 감이 오지 않아서 다른 사람의 소스코드를 보고 분석하였다.
[소스코드]
원본 소스코드 주소 : https://suri78.tistory.com/128
import sys
# 테스트 케이스 갯수
testcase = int(sys.stdin.readline())
# 테스트 케이스 갯수만큼 데이터 입력받음
for _ in range(testcase):
# n = 총 학생의 수
n = int(sys.stdin.readline())
# 선택된 학생의 리스트 choice와 방문여부를 저장하는 visited 리스트
choice = [0] + list(map(int, sys.stdin.readline().split()))
visited = [0] * (n + 1)
# 연결된 그래프의 갯수
group = 1
# 총 학생의 수 만큼 순회
for i in range(1, n + 1):
# 만약 i번 학생의 선택지에 방문하지 않았다면(visited[i]가 0이라면)
if visited[i] == 0:
# visited[i]가 0일 때까지
while visited[i] == 0:
# i번쨰 학생 방문여부에 group변수의 값을 대입하고
visited[i] = group
# i 를 i번쨰 학생이 선택한 학생의 번호로 바꾼다.
i = choice[i]
#만약 visited[i]가 group 변수와 같다면
while visited[i] == group:
# visited[i]를 -1로 바꿔주고
visited[i] = -1
# i를 i번째 학생이 선택한 학생의 번호로 바꾼다.
i = choice[i]
#그리고 group 변수의 값에 1을 추가한다.
group += 1
# 총 이어진 그래프의 갯수를 담을 count 변수
count = 0
#방문 리스트를 모두 돌아
for v in visited:
# 만약 리스트 값이 0보다 크다면 (즉 이어진 그래프가 되었다면)
if v > 0:
# count 변수에 1을 추가
count += 1
# 카운트 변수 출력
print(count)이번 문제는 연결된 그래프의 갯수를 세는 것이 주된 풀이 방법이다. 위의 코드에서 group변수와 visited리스트를 통해 해당 인덱스 번째의 학생이 고른 학생과 골라진 학생이 고른 또다른 학생 ... 그리고 제일 마지막 학생이 고른 학생의 번호가 제일 첫번쨰 고른 학생의 번호라면, (간단히 말해서 순회를 다 돌았는데 처음 시작점으로 돌아왔다면) 해당 연결들은 하나의 연결된 그래프를 이루게 되기 때문에 같은 group 변수값을 대입받고, 만약 이어지지 않는다면 해당 연결들은 연결된 그래프를 형성하지 않기 때문에 group 변수의 값에 1을 추가해서 다음 그래프를 찾을 때 혼선을 줄이는 것이다. 또한 이어진 그래프들은 전부 0보다 큰 group 변수 값을 대입받았기 떄문에 -1을 대입받은 이어지지 않은 그래프들의 숫자만 구해준다면 이 문제의 정답을 도출할 수 있다.
