삼성 SW 역량 테스트

[삼성 sw 역량 테스트 A형 샘플 문제] 프로세서 연결하기 c++

dfs로 전선 연결이 필요한 모든 프로세서 들이 전설을 이을 모든 경우의 수를 따져서 구했다. 여기서, 만약 해당 프로세서가 벽으로 도달하지 못하는 경우를 계산하여 백트래킹( 가지치기) 를 수행하였다. 추가로, 이 문제에선,'모두 연결 가능 할시의 최단 거리' 가 아니라, '최대한 많은 개수를 연결할 시 의 최단거리' 를 구해야한다. 따라서, dfs를 통해 해당 프로세서를 '상','하','좌','우' 로 연결하는 가능성에 더해, '해당 프로세서를 연결하지 않는 가능성' 도 체크해야한다. 예시 위와 같이 입력이 들어온 경우, 우리가 전선으로 연결해줘야하는, 파란 동그라미 표시를한 프로세서에 대해 전선의 연결 가능성을 확인해야한다. 하지만, 맨위의 파랑 원은, 다른 전선들이 연결되면, 필연적으로 벽에 닿을 ..