[Programmers 코딩테스트 고득점 Kit] 방의 개수

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/49190

코딩테스트 연습 - 방의 개수

arrows 벡터 크기가 최대 100,000이므로 이차원 배열 대신 map을 사용해야하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 정점과 간선을 나타내는 구조체를 정의하고 해당 구조체에 대한 visited map을 선언해줍니다.

2. arrows 벡터를 순회하면서 정점과 간선들을 방문했다고 표시해줍니다.

2.1 해당 정점은 이미 방문했지만 아직 해당 간선을 방문하지 않은 상태라면 사이클을 형성한 것이므로 방 개수를 하나 늘려줍니다.

2.2 아래 그림처럼 1 * 1 정사각형 내 두 개의 방이 있는 케이스도 있으므로 간선을 두 배씩 늘려주면서 방 개수를 파악해야합니다.

3. 2번에서 구한 방 개수를 반환해줍니다.

 

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~