[BOJ] 백준 14502 연구소 (JAVA)

삼성 SW 역량테스트 기출..

---

📑 문제

 

백준 14502 연구소

 

---

🌱 아이디어

지도의 크기 (3 ≤ N, M ≤ 8), 입력되는 값이 적다! = 완탐 가능하다.

지도의 최대 크기가 8*8 = 64 이다. 완전탐색 으로 풀 수 있다는 뜻이다,

즉 지도에 벽을 3개를 모든 경우만큼 다 세운 후 가장 많은 안전구역의 크기를 구하면 된다!

DFS, BFS 둘 다 사용해서 풀 수 있다

DFS = 벽 세우기, BFS = 바이러스 퍼트리기 이렇게 역할을 나눠서 구현할 수 있다.

 

---

🌱 코드 및 풀이

 

엄청 길다;;; 하지만 각 기능을 함수로 나눠서 설명을 달아 놨으니 천천히 보신다면 이해하기엔 어려움이 없을 것이다

아마도 이해가 안 된다면 댓글 달아주시면 최대한 설명해 보겠습니다.

그래도 간단히 설명을 하자면

 

dfs() -> 지도에 벽을 3개를 세운다

bfs() -> 바이러스를 전염시킨다.

cntSafe() -> 안전구역 카운트 및 최댓값 도출

cloneCopy -> 벽이 세워진 형태는 유지(dfs()에서 다시 사용해야 하기 때문) 바이러스의 초기값으로 초기화

 

이런 흐름으로 문제를 풀었다. 되게 복잡하게 풀었지만 함수를 통해 기능을 나눈다면 

구현할 때 큰 어려움은 없다고 생각한다 ㅎㅎ

---

🌱 느낀 점

완탐으로 해도 충분히 풀 수 있다.

 

기본적으로 삼성 SW 역량 기출문제들은 하나의 알고리즘만 사용하는 것 이 아닌 하나 이상의 알고리즘

을 사용하는 것 같다.

입력되는 수가 적다면 완전탐색을 생각하고  알고리즘을 어떤 것을 사용할지 생각하는 훈련을 해야겠다!