이번 문제는 주어진 통로와 벽에 대한 길이 2짜리 선분을 안겹치게 가장 많이 찾아내는 문제였다. 처음에는 백트레킹으로 구현하였고, 주어진 테스트 케이스에 대하여 답이 도출되었지만, 재귀가 터지는 에러가 발생하였다. 이를 보고 다른 방법으로 풀어봐야겠다고 생각하였다.

다른 방법으로 그냥 왼쪽 위에서부터 오른쪽 아래로 내려가며 선분의 길이가 2가 되는 경우에 모두 체크하는 방법으로 문제를 풀었다. 벽의 방향을 0, 1, 2, 3으로 잡고, 겹치는지의 여부를 판단할 때 사용하였는데, 처음에는 이를 좌표와 방향으로 된 튜플로 저장하여 사용했다. 그러나 이 방법은 다시 한번 튜플로 이뤄진 리스트를 순회해야 했기 때문에 시간초과가 발생하였고, 바로바로 겹치는 여부를 확인하고, 바로바로 값을 취하는 방식으로 해결할 수 있었다.

Code

백트레킹을 이용한 풀이 (fail)

m, n = map(int, input().split())
grid = [str(input()) for _ in range(m)]
possible = []
for i in range(m):
    for j in range(n):
        # 0, 1, 2, 3 : 상, 하, 좌, 우
        if grid[i][j] == '.':
            if 0 <= j+1 < n and grid[i][j+1] == '.':
                if 0 <= i+1 < m and grid[i+1][j] == 'X' and grid[i+1][j+1] == 'X':
                    possible.append((i+1, j, i+1, j+1, 0))
                if 0 <= i-1 < m and grid[i-1][j] == 'X' and grid[i-1][j+1] == 'X':
                    possible.append((i-1, j, i-1, j+1, 1))
            if 0 <= i+1 < m and grid[i+1][j] == '.':
                if 0 <= j+1 < n and grid[i][j+1] == 'X' and grid[i+1][j+1] == 'X':
                    possible.append((i, j+1, i+1, j+1, 2))
                if 0 <= j-1 < n and grid[i][j-1] == 'X' and grid[i+1][j-1] == 'X':
                    possible.append((i, j-1, i+1, j-1, 3))
answer = 0
pictures = []
def find_max(cur, cnt):
    global answer
    if cur==len(possible):
        answer = max(answer, cnt)
        return
    if (possible[cur][0], possible[cur][1], possible[cur][4]) not in set(pictures) and (possible[cur][2], possible[cur][3], possible[cur][4]) not in set(pictures):
        pictures.append((possible[cur][0], possible[cur][1], possible[cur][4]))
        pictures.append((possible[cur][2], possible[cur][3], possible[cur][4]))
        find_max(cur+1, cnt+1)
        pictures.pop()
        pictures.pop()
        find_max(cur+1, cnt)
    else:
        find_max(cur+1, cnt)
find_max(0, 0)
print(answer)

정답 풀이

m, n = map(int, input().split())
grid = [str(input()) for _ in range(m)]
using = [[[False for _ in range(n)] for _ in range(m)] for _ in range(4)]
answer = 0
def find_max():
    global answer
    for i in range(1, m-1):
        for j in range(1, n-1):
            if grid[i][j] == '.':
                if grid[i][j+1] == '.':
                    if grid[i+1][j] == 'X' and grid[i+1][j+1] == 'X' and not using[0][i][j]:
                        using[0][i][j] = True
                        using[0][i][j+1] = True
                        answer += 1
                    if grid[i-1][j] == 'X' and grid[i-1][j+1] == 'X' and not using[1][i][j]:
                        using[1][i][j] = True
                        using[1][i][j+1] = True
                        answer += 1
                if grid[i+1][j] == '.':
                    if grid[i][j+1] == 'X' and grid[i+1][j+1] == 'X' and not using[2][i][j]:
                        using[2][i][j] = True
                        using[2][i+1][j] = True
                        answer += 1
                    if grid[i][j-1] == 'X' and grid[i+1][j-1] == 'X' and not using[3][i][j]:
                        using[3][i][j] = True
                        using[3][i+1][j] = True
                        answer += 1
find_max()
print(answer)