https://www.acmicpc.net/problem/17142
17142번: 연구소 3
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는
www.acmicpc.net
삼성 SW역량테스트 기출문제였다고 한다.
BFS와 DFS를 모두 사용하는 문제라고 하는데,
Python에서는 '경우의 수'를 뽑아내는 내장함수인 combinations를 활용하면 한 줄로 해결할 수 있다.
일반적인 BFS로 문제를 풀면 채점 99% 단계에서 오답 처리가 된다.
오답을 만들어내는 반례는 https://mygumi.tistory.com/352 이곳에서 상세한 설명을 해 주셨다.
백준 17142번 연구소 3 :: 마이구미
이 글은 백준 알고리즘 문제 17142번 "연구소 3" 를 풀이한다. 삼성 SW 역량 테스트 문제이다. 문제 해결을 위해 DFS, BFS 2가지 모두 요구한다. 문제 링크 - https://www.acmicpc.net/problem/17142 DFS, BFS - h..
mygumi.tistory.com
어떻게 코드를 바꿔야 답을 찾게 할 수 있는지 한참을 고생했는데, 생각보다 간단하게 풀렸다.
결국 '빈 공간을 바이러스에 감염시키는 마지막 시점'만 반환하면 된다. 그게 정답이니까.
내가 BFS 코드 만드는 방식이 효율성에 문제가 있는 것 같다.
다른 삼성 SW역량테스트 기출문제에서도 비슷한 방식으로 BFS 코드를 만들었더니 시간초과가 자꾸 난다.
왜케 어렵누
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 프로그래머스. 짝지어 제거하기 (Level 3) (0) | 2019.10.31 |
|---|---|
| [Python] 프로그래머스. 가장 먼 노드 (Level 3) (0) | 2019.10.30 |
| [Python] 프로그래머스. 2018 카카오 Recruit - 추석 트래픽 (0) | 2019.10.28 |
| [Python] 백준 17298. 오큰수 (0) | 2019.10.27 |
| [Python] 프로그래머스. 숫자 게임 (Level 3) (0) | 2019.10.26 |