알고리즘 알고파! 알고라파덕
안녕하세요~ 알고라파덕입니다!
이번 문제는 오리바이러스라는 문제입니다!
저는 흠.. 약간 BFS같은 느낌으로 풀어보았습니다~
- 문제 개요
테스트 케이스가 입력으로 주어지면 먼저 오리의 수 N이 주어지고 NxN 오리들끼리의 친구관계가
주어집니다. 그리고 여기서 또 테스트 케이스가 나와 개수만큼 처음 바이러스을 갖는 오리의 번호가
입력됩니다. 그럼 여기서 처음 2마리의 오리가 바이러스를 다 퍼트렸을 때 감염된 오리의 수를
구해주시면 됩니다.
- 문제 풀이
먼저 오리들의 친구 관계를 인접 행렬 리스트로 바꾸어 줍니다.
인접 행렬 리스트란 0번째 열에 연결된 노드의 개수, 그리고 1~노드의 개수까지
연결된 노드의 번호를 저장합니다. 인접 행렬 리스트도 따로 블로그에 포스팅하겠습니다.
이렇게 인접 행렬 리스트를 만들고 이제 ORI라는 배열을 만듭니다.
ORI라는 배열은 감염된 오리를 저장하는 배열입니다. ORI배열의 크기 즉 감염된 오리의
수를 ORIVIRUS라는 변수로 처음 2마리로 설정합니다.
이제부터 ORI배열의 처음부터 끝까지 ORIVIRUS까지 탐색을 하면서 ORI[i]와 친구인 오리들을
CHK배열을 하나씩 ++해줍니다. 단 처음 감염된 오리는 -200으로 바꾸어줍니다.
이를 반복하다 CHK배열의 값이 2가 되었다는 것은 오리의 친구가 2마리라는 것이므로
이 번째 오리를 ORI배열에 추가시켜주고 ORIVIRUS 총 감염수를 증가시킵니다.
그럼 다음에 ORI배열에 있는 감염된 오리로 또 친구인 오리들의 CHK를 ++하여 감염된 오리를
모두 찾아낼 수 있습니다.
소스가 필요하신다면 댓글을 달아주세요~
출처 : https://algospot.com/judge/problem/read/ORIVIRUS