테트로미노
https://www.acmicpc.net/problem/14500
삼성 기출문제이다. 매우 어려운 문제였다.
처음에, 도형의 모든 경우의 수를 하나 하나 놓아봐서 최대값을 구해야하는지 생각했다.
하지만, DFS로 해결할 수 있다.
풀이
다음 그림과 같이 DFS를 이용하여 최대한 깊이 탐색한다.
ㅗ 모양을 제외한 모양은 DFS로 탐색이 가능하다. 4개의 탐색(깊이 3) 까지 마쳤을 때, 최대값을 계산한다.
로봇청소기
https://www.acmicpc.net/problem/14503
삼성 기출문제이다.
매우 어려운 문제였다. 문제 이해 자체가 어렵다.
BFS로 해결할 수 있다.
풀이
현재 위치를 청소한다.
현재위치에서 바라보는 방향의 왼쪽 방향을 확인한다.
( 이 작업을 4번 진행한다. 그렇다면, 현재위치의 동서남북 모든 방향을 확인 할 수 있다.)
청소를 해야할 구역이고, 아직 방문하지 않았으면 방문한다.
네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진한다.
네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
다음 그림에서와 같이 처음 시작은 (7,4) 에서 시작하고, 방향은 북쪽(0)을 바라보고 있다고 하자.
최종 움직임은 다음과 같이 그려질 것이다.
감시
https://www.acmicpc.net/problem/15683
어려웠다. BFS로 시도하였지만, 실패하였다.
해설을 보고 DFS로 풀었다.
풀이
- 이전 감시 상태를 가져와 복사한다. (깊은 복사)
- 감시 가능 지역을 표시한다.
- 다음 cctv를 탐색한다.
탐색 순서를 설명하기 위해 다음 표를 보자.
위의 표에서 감시 카메라는 A, B, C 세 개가 있다.
A와 B 는 상하 / 좌우 를 감시할 수 있고, C는 상하좌우를 감시할 수 있다.
탐색 순서는 다음 그림과 같이 나타낼 수 있다.
콩 많이 심기
https://www.swexpertacademy.com/main/code/problem/problemDetail.do
SW Expert Academy [D4]
정답 풀이
모든 판에 콩을 심었다고 가정하고 시작한다.
콩이 심은 판 사이의 거리가 2이면 콩을 지운다.
위의 그림처럼, 빨간색 원이 기준이 된다.
기준을 중심으로 길이가 2인 판에 콩이 있으면 콩을 없앤다. 파란색 네모 부분이 길이가 2인 지점이다.
그리고 기준을 다음 칸으로 옮겨서 같은 작업을 반복한다.
정답 코드
