백준 17085 십자가 2개 놓기 문제 풀이

Posted on | In
백준 17085 십자가 2개 놓기 파이썬 완전 탐색 풀이

https://www.acmicpc.net/problem/17085

문제 풀이

주어진 크기의 판 내에서 2개의 십자가의 크기 곱이 가장 큰 값이 나오도록 해야하는 문제이다. 격자판의 크기는 최대넓이가 225칸 이므로 브루트포스 방식으로 풀어도 충분히 2초내가 나온다. 하지만 풀이 과정이 복잡해서 좀 어려웠던 문제이다.

1. 각 점마다 정보 탐색

우선 N*M 의 보드판을 순회하면서 각 점이 #이면 해당 점에서 최대 확장 가능한 넓이를 구해서 해당 점의 위치(row, col)와 최대 확장 길이를 dotInfo 배열에 추가한다.

2. 2개의 크기 간 유효성 검사

그 다음 dotInfo 에 들어간 배열들끼리 비교하면서 우선 비교할 십자가를 배열에 1로 저장한 뒤, 두 번째 십자가를 길이만큼 확장시키면서 겹치는지 검사해서 안 겹친다면 두 넓이의 곱을 result에 저장한다.

(여기서 유효성 검사 전에 2개의 십자가의 크기를 미리 곱한 뒤에 현재 result보다 클 경우에만 유효성 검사를 하면 불필요한 계산을 단축시킬 수 있다)

3. 추가로 고려해야 할 사항

당연히 해당 부분까지 완료하면 맞을거라고 생각하고 제출해봤는데 50% 부근즈음에서 오답이 났다.. 그래서 몇시간동안 각종 예시를 들며 찾아보았는데 해당 점에서 무조건 최대 크기의 정보만 저장하면 안된다는 것이다. 작은 것 끼리 곱해서 더 큰 경우가 나올 수 있기 때문이다.

예를 들어 아래의 코드에서 정답은 25 인데 최대크기만 저장하면 크기가 9와 1인게 곱해져서 9가 되므로 오답이 난 것이였다.

1
2
3
4
5
6
7
8
5 8
..#..#..
..#..#..
########
..#..#..
..#..#..

실제 정답은 25 이지만 내가 제출한 코드는 9가 나왔다.

그래서 1번 과정에서 dotInfo 에 최대 크기만 저장하는것이 아닌 1부터 최대크기 까지를 저장하니까 해결됐다.

소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 해당 점에서 최대 크기를 구하고 정보를 넣는 함수
def search(row, col):
    size = 0
    while -1 < row-size and row+size < N and -1 < col-size and col+size < M and board[row-size][col] == board[row+size][col] == board[row][col-size] == board[row][col+size] == '#':
        size += 1
    while size:  # 작은 경우끼리 곱하는게 더 클 수도 있으므로 고려해야함
        dotInfo.append([size, row, col])
        size -= 1

# 점 2개 부분이 서로 안겹치는지 유효성 검사
def test(dot1, dot2):
    testBoard = [[0]*M for _ in range(N)]
    d = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    for i in range(dot1[0]):
        for j in range(4):
            testBoard[dot1[1]+d[j][0]*i][dot1[2]+d[j][1]*i] = 1

    for i in range(dot2[0]):
        for j in range(4):
            if testBoard[dot2[1]+d[j][0]*i][dot2[2]+d[j][1]*i] == 1:
                return False # 겹친다면 False 반환
    return True

N, M = map(int, input().split())
board = []
dotInfo = []
result = 0
for _ in range(N):
    board.append(str(input()))

for r in range(N):
    for c in range(M):
        if board[r][c] == '#':
            search(r, c) # #인 부분 정보 저장

for i in range(len(dotInfo)-1):
    for j in range(i+1, len(dotInfo)):
        mul = (1+(dotInfo[i][0]-1)*4)*(1+(dotInfo[j][0]-1)*4)
        # 현재 값보다 큰 경우만 test로 유효성 검사
        if mul > result and test(dotInfo[i], dotInfo[j]):
            result = mul

print(result)