[DFS] 백준#14500: 테트로미노/Python

📝 문제

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

14500번: 테트로미노

💡 접근법

DFS 알고리즘을 활용하여 문제를 해결하였습니다. DFS를 통해 특정 좌표에 상하좌우 방면으로 3개의 블록을 이어 붙이면 'ㅏ', 'ㅓ', 'ㅗ', 'ㅜ' 모양을 제외한 모든 테트로미노를 만들 수 있습니다. 'ㅏ', 'ㅓ', 'ㅗ', 'ㅜ' 모양의 테트로미노는 2번째 블록까지 붙였을 때 새로운 블록에서 이어붙일 다음 블록을 탐색하지 않고 다시 기존 블록 위치에서 탐색하도록 로직을 작성하면 만들 수 있습니다.

💻 코드

1) 전체 코드

import sys; input = sys.stdin.readline

def dfs(x, y, step, total):
    global answer
    # 종료조건1) 탐색을 계속 진행하여도 최댓값에 못 미치는 경우
    if total + max_val*(4-step) <= answer:
        return

    # 종료조건2) 블록 4개를 모두 활용한 경우
    if step == 4:
        answer = max(answer, total)
        return

    # 상하좌우 방향으로 블록 이어 붙여 나가기
    for dx, dy in d:
        nx = x + dx # 새로운 x 좌표
        ny = y + dy # 새로운 y 좌표
        # 새로운 좌표가 유효한 범위 내 있고 탐색이력이 없는 경우
        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
            # 2번째 블록 연결 후 'ㅏ','ㅓ','ㅗ','ㅜ' 만들기
            if step == 2:
                visited[nx][ny] = True # 탐색기록
                # 새로운 좌표에서 탐색하지 않고 기존 좌표로 돌아와 탐색재개
                dfs(x, y, step+1, total+board[nx][ny])
                visited[nx][ny] = False # 탐색기록 제거

            visited[nx][ny] = True
            dfs(nx, ny, step+1, total+board[nx][ny])
            visited[nx][ny] = False

if __name__ == "__main__":
    N, M = map(int, input().split()) # 좌표의 행, 열 개수
    board = [list(map(int, input().split())) for _ in range(N)] # 좌표별 값
    max_val = max(map(max, board)) # 모든 좌표 중 최댓값
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 좌표 내 상하좌우
    visited = [[False] * M for _ in range(N)] # 탐색여부 확인용
    answer = 0

    for i in range(N):
        for j in range(M):
            visited[i][j] = True # 탐색기록
            dfs(i, j, 1, board[i][j])
            visited[i][j] = False # 탐색기록 제거
    print(answer)

2) 해설

(1) 데이터 입력 속도 개선

import sys; input = sys.stdin.readline

파이썬 내장함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline을 사용하였습니다.

(2) DFS 함수

def dfs(x, y, step, total):
    global answer
    # 종료조건1) 탐색을 계속 진행하여도 최댓값에 못 미치는 경우
    if total + max_val*(4-step) <= answer:
        return

    # 종료조건2) 블록 4개를 모두 활용한 경우
    if step == 4:
        answer = max(answer, total)
        return

    # 상하좌우 방향으로 블록 이어 붙여 나가기
    for dx, dy in d:
        nx = x + dx # 새로운 x 좌표
        ny = y + dy # 새로운 y 좌표
        # 새로운 좌표가 유효한 범위 내 있고 탐색이력이 없는 경우
        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
            # 2번째 블록 연결 후 'ㅏ','ㅓ','ㅗ','ㅜ' 만들기
            if step == 2:
                visited[nx][ny] = True # 탐색기록
                # 새로운 좌표에서 탐색하지 않고 기존 좌표로 돌아와 탐색재개
                dfs(x, y, step+1, total+board[nx][ny])
                visited[nx][ny] = False # 탐색기록 제거

            visited[nx][ny] = True
            dfs(nx, ny, step+1, total+board[nx][ny])
            visited[nx][ny] = False

시간 복잡도를 고려하여 2가지 종료 조건을 추가하였습니다.

• 첫째, 블록을 더 붙이더라도 이전에 구한 좌표값들의 총합 중 최댓값(answer)을 넘지 못하는 경우
• 둘째, 블록은 총 4개이므로 4개의 블록을 모두 조합한 경우

위의 종료 조건을 만족하지 않으면, 반복문을 통해 특정 좌표에서 상하좌우 방향으로 이어 붙일 블록을 탐색합니다. 2번째 블록까지 이어 붙였다면 'ㅏ', 'ㅓ', 'ㅗ', 'ㅜ' 블록도 만들 수 있도록 로직을 작성해야 합니다. 이때 사용한 방법이 3개의 연이은 블록(i.e., ㅁㅁㅁ) 중간에 블록 1개를 추가로 붙이되 탐색하는 좌표는 실제로 변화시키지 않는 것입니다. 즉, 중간에 블록을 추가로 붙였다면 해당 블록에서 탐색을 재개하지 않고, 해당 블록을 붙인 기존의 블록에서 탐색을 재개하도록 로직을 작성하면 됩니다. 이외 다른 모양의 테트로미노는 상하좌우 방향으로 탐색하고 블록을 이어붙이면 만들 수 있습니다. 따라서, 일반적인 재귀 함수를 활용하는 DFS처럼 새로운 좌표를 함수에 재귀적으로 전달하여 로직을 완성하였습니다.

(3) 메인함수

if __name__ == "__main__":
    N, M = map(int, input().split()) # 좌표의 행, 열 개수
    board = [list(map(int, input().split())) for _ in range(N)] # 좌표별 값
    max_val = max(map(max, board)) # 모든 좌표 중 최댓값
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 좌표 내 상하좌우
    visited = [[False] * M for _ in range(N)] # 탐색여부 확인용
    answer = 0

    for i in range(N):
        for j in range(M):
            visited[i][j] = True # 탐색기록
            dfs(i, j, 1, board[i][j])
            visited[i][j] = False # 탐색기록 제거
    print(answer)

✅ 채점결과

정답 확인

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/dfs-bfs/boj_14500.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

📚 참고할 만한 포스팅

문제 풀이에 사용한 DFS 알고리즘에 대한 자세한 내용은 아래의 포스팅을 참고해 주세요!

https://heytech.tistory.com/55

[알고리즘] 깊이 우선 탐색(DFS) 알고리즘에 대해 알아보자!(+Python 구현)

---

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.