백준 / 14500번 테트로미노- 백트래킹, dfs / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 테트로미노

문제 사이트: https://www.acmicpc.net/problem/14500

 

 

 

이미지 참고 : https://wikidocs.net/217631 근데 여기 코드는 시간 초과남, 방문처리때문인듯

---

나의 풀이 - 첫번째 풀이 시간초과

import sys

input = sys.stdin.readline

N,M = map(int,input().split())
direct = ((-1,0),(1,0),(0,-1),(0,1)) # 상하좌우
maps = []
max_sum = 0
for i in range(N):
    # 종이에 쓰여 있는 수
     maps.append(list(map(int,input().split())))

def dfs(visited_points,cnt,total):
    global max_sum
    # 백트래킹은 dfs
    if cnt == 4:
        if max_sum < total:
            max_sum = total
        return
    else:
        for y,x in visited_points:
            for i in range(4):
                ny = y + direct[i][0]
                nx = x + direct[i][1]
                if [ny,nx] not in visited_points and 0 <= ny < N and 0 <= nx < M:
                    visited_points.append([ny,nx])
                    dfs(visited_points,cnt + 1,total + maps[ny][nx])
                    visited_points.pop()  # 백트래킹 (for 문 안이라서 pop 안해주면 list 에 누적됨)
for i in range(N):
    for j in range(M):
        dfs([[i,j]],1,maps[i][j])
# 출력: 테르노미노가 놓인 칸의 수들의 합(합을 최대로 해야함)
print(max_sum)

 

> 방문처리를 매번 리스트에 넣어두고 진행해서 에러남

> 전역으로 관리해야함

> ㅗ, ㅜ , ㅓ, ㅏ 와 같은 스페셜 케이스 관리

 

모범답안(두번쨰 풀이)

import sys

input = sys.stdin.readline

N,M = map(int,input().split())
direct = ((-1,0),(1,0),(0,-1),(0,1)) # 상하좌우

maps = []
max_sum = 0
visited = [[False] * M for _ in range(N)]
for i in range(N):
    # 종이에 쓰여 있는 수
     maps.append(list(map(int,input().split())))

def dfs(y,x,cnt,total):
    global max_sum
    global visited
    # 백트래킹은 dfs
    if cnt == 4:
        if max_sum < total:
            max_sum = total
        return
    else:
        for i in range(4):
            ny = y + direct[i][0]
            nx = x + direct[i][1]
            if 0 <= ny < N and 0 <= nx < M and visited[ny][nx] == False:
                visited[ny][nx] = True
                dfs(ny,nx,cnt + 1,total + maps[ny][nx])
                visited[ny][nx] = False

def check_other_case(y,x):
    # ㅗ,ㅜ,ㅓ,ㅏ 확인
    global visited, max_sum
    case = [((0, 0), (0, 1), (0, -1), (1, 0)) ,  # ㅜ
            ((0, 0), (0, 1), (0, -1), (-1, 0)),  # ㅗ
            ((0, 0), (-1, 0), (1, 0), (0, -1))  ,  # ㅓ
            ((0, 0), (-1, 0), (1, 0), (0, 1))]  # ㅏ
    for c in case:
        tmp_sum = 0
        for i in range(4):
            ny = y + c[i][0] 
            nx = x + c[i][1]
            if 0 <= ny < N and 0 <= nx < M:
                tmp_sum += maps[ny][nx]
            else:
                break
        if max_sum < tmp_sum:
            max_sum = tmp_sum



for i in range(N):
    for j in range(M):
        visited[i][j] = True
        dfs(i,j,1,maps[i][j])
        visited[i][j] = False # 백트래킹
        check_other_case(i,j)

# 출력: 테르노미노가 놓인 칸의 수들의 합(합을 최대로 해야함)
print(max_sum)

---

※ 알아야 할 것

- visited 로 True, False 제대로 지정해줘서 전역으로 방문처리 관리하면 메모리가 많이 안참(시간초과X)

- for 문 안에서는 백트래킹으로 꼭 pop을 해주자

- 스페셜 케이스도 잘 고려할 것