백준 17472번 다리 만들기 2

문제 링크입니다: https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

다리의 방향도 고려해야하기 때문에 생각보다 까다로운 시뮬레이션 문제였습니다.

코드를 깔끔하게 짠다고 노력했는데도 불구하고 상당히 지저분하기 때문에 주석을 최대한 꼼꼼하게 달았습니다.

 

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

1. 섬으로 표기된 지역 즉, 1로 표시된 좌표를 모두 islands 벡터에 추가해줍니다.

2. islands 벡터에 있는 좌표를 순차적으로 확인하며 아래 혹은 오른쪽 혹은 양방향으로 다리를 배치해줍니다.

2.1 이 때, 아래와 오른쪽으로만 다리를 배치하는 이유는 좌표를 좌상단부터 우하단 순으로 입력을 받았고 islands 벡터에도 동일한 순서대로 좌표가 추가되어있기 때문에 반대 방향을 확인할 필요가 없습니다. (반대방향으로 다리를 놓을 수 있을 경우 이미 전 좌표에서 다리를 배치했을 것이라고 그리디하게 판단합니다.)

3. isAllVisited 함수를 통해 모든 섬이 연결되어 있는지 확인하고 만약 모든 섬이 연결되어 있다면 result를 업데이트해줍니다.

 

개발환경:Visual Studio 2019

 

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