[알고스팟/ALGOSPOT] 6. BOARDCOVER

 

 

 

알고리즘 알고파! 알고라파덕

안녕하세요~ 알고라파덕입니다!

 

6번 문제는 BOARDCOVER라는 문제입니다!

 

저는 이 문제를 재귀함수로 DFS(깊이 우선 탐색법)를 구현하여 풀었습니다.

 

• 문제 개요

 

입력에서 테스트 케이스가 주어지면 하나의 테스트 케이스당 (NxM)행렬의 게임판이 주어집니다.

 

이 게임판에서 '#'은 블록이 있는 부분이고, '.'은 블록이 없는 부분입니다.

 

그럼 저희는 블록이 없는 부분 '.'을 '#'으로 채워주어야 합니다!

 

블록의 개수는 ㄱ, ㄴ과 ㄱ, ㄴ의 90도 회전한 블록 4개가 있습니다.

 

• 문제 풀이

 

재귀함수를 이용하여 DFS를 구현하였습니다.

 

먼저 입력을  받을 때 블록이 없는 부분 '.'부분을 추출해 놓으면 속도를 더 빠르게 할 수 있습니다.

 

탐색도 쉽게 할 수 있구요!

 

예를 들어 입력을 받으면서 '.'이 부분이 오면 하나의 배열을 만들어서 '.'부분의 행과 열을

 

저장합니다. 구조체를 쓰셔도 되구요! 예를 들면 a[cnt].x, a[cnt].y 이런 식으로

 

'.'의 개수마다 a[cnt].x, a[cnt].y가 입력을 받게 됩니다.

 

cnt가 3의 배수가 아니라면 블록을 채울수 없는 경우이므로 0을 출력합니다.

 

이제 DFS 깊이 우선 탐색법을 적용할텐데요.

 

위에서부터 첫 번재 '.'에서 DFS를 시작합니다.

 

(A[0].X, A[0].Y) 위치에서 블록을 채울 수 있는 경우를 확인합니다.

(row    ,  col     )

블록을 채울 수 있다는 것은

 

ㄱ 같은 경우에는 data[row][col], data[row][col+1], data[row+1][col+1]의 값이 '.'이

되어야 하고 row+1 <= n 그리고 col+1 <= m 게임판을 벗어나지 않는 경우에서

 

ㄴ 같은 경우에는 data[row][col], data[row+1][col], data[row+1][col+1]의 값이 '.'이

되어야 합니다. row+1 <= n 그리고 col+1 <= m

 

ㄱ의 좌우로 한번접은 모양 같은 경우에는 data[row][col], data[row][col+1], data[row+1][col]이

'.'이 되어야 합니다. row+1 <= n 그리고 col+1 <= m 

 

ㄴ의 좌우로 한번접은 모양 같은 경우에는 data[row][col], data[row+1][col-1], data[row+1][col]이

'.'이 되어야 합니다.row+1 <= n 그리고 col-1 >= (1 or 0) 게임판을 벗어나지 않는 경우에만 판단. 

 

이 경우에 만족을 한다면 data값이 '.'인 부분을 '#'으로 바꾸어주고 다음 '.'위치로 이동을 합니다.

 

이동은 A[]배열을 활용하여 A[]배열에 있는 위치가 '.'인 곳으로 들어갑니다. 그 후 그 위치에서도

 

마찬가지로 저 경우의 수를 만족한다면 data의 '.'인 부분을 '#'으로 바꾸어주고 다음 '.' 위치로

 

이동합니다.

 

하지만 (row,col) 위치에서 4가지 경우가 만족하지 않는다면 채울수 있는 경우가 아니기 때문에

 

return을 하면서 '#'으로 바꾸어준 부분을 '.'으로 다시 바꾸어줍니다.

 

모든 블록을 다 채워놓았으면 경우의 수를 증가시키고 리턴을 하여 다른 경우를 찾습니다.

 

이 과정을 반복하면 모든 경우의 수를 확인할 수 있고 최종적으로 총 가지수를 출력할 수 있습니다.

 

정확히 이해가 되지 않으신다고 하시면, 탐색과정을 동영상을 찍어 올려드리겠습니당~!

 

출처 : https://algospot.com/judge/problem/read/BOARDCOVER