[Codeforces] 1722F. L-shapes [Round #817 (Div.4)]

📚 문제 F: L-shapes

📖 풀이

대회 중에는 테스트 케이스는 다 맞게끔 풀었는데 히든 케이스에서 틀렸던 문제이다.

DFS로 L모양으로 이루어져있는지 파악한다.

1. DFS로 연결된 개수가 3개인지 확인한다.
2. 연결된 타일들을 확인할 때 그 때의 방향을 기억해 담아준다.
3. 확인했던 방향을 또 확인하면 일자로 3개가 붙는 경우이니 이 때를 처리해준다.(나는 같은 방향이 또 나오면 4를 리턴해 3개가 아닌 수가 나와 틀렸다고 처리했다.)
4. DFS로 확인했던 타일은 방문처리해서 다시 확인하지 않는다.

각 타일의 대각선에 타일이 2개가 있는지 확인한다. 2개말고 다른 수가 나오면 틀린 것이다.

이 때는 방문처리 상관없이 확인하면 된다.

📒 코드

def in_range(x, y):
    return 0 <= x < h and 0 <= y < w


def check(x, y):
    dx, dy = [0, 1, 1, 1, 0, -1, -1, -1], [1, 1, 0, -1, -1, -1, 0, 1]
    cnt = 1     # 현재 타일 주변(대각선 포함) 타일 개수 확인
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if in_range(nx, ny) and arr[nx][ny] == "*":
            cnt += 1

    if cnt == 3:
        return True
    else:
        return False


def dfs(x, y, dir_arr):      # 인접한 타일 개수 파악(대각선 X)
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
    cnt = 1
    visited[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if in_range(nx, ny) and arr[nx][ny] == "*" and not visited[nx][ny]:
            if i in dir_arr:        # 이미 나온 방향이 또 나온 경우는 잘못된 값인 4를 리턴
                return 4
            dir_arr.append(i)
            cnt += dfs(nx, ny, dir_arr)
    return cnt


def sol():
    for i in range(h):
        for j in range(w):
            if arr[i][j] == '*':
                if not visited[i][j]:
                    if dfs(i, j, []) != 3:
                        return 'NO'
                if not check(i, j):
                    return 'NO'
    return 'YES'


t = int(input())
for _ in range(t):
    h, w = map(int, input().split())
    arr = [list(input()) for _ in range(h)]
    visited = [[0 for _ in range(w)] for _ in range(h)]
    print(sol())

🔍 결과

코드를 입력하세요