[백준] 14500번: 테트로미노 (파이썬)

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

 

문제를 읽고, BFS가 먼저 생각났다.

from collections import deque
n,m = map(int,input().split())
graph = [ list(map(int,input().split())) for _ in range(n)]

#방향
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

4방향을 탐색해야 하므로, 방향 리스트를 만들어 준다.

result = 0

for i in range(n):
    for j in range(m):
        score = search(i,j)
        result = max(result, score)
print(result)

모든 좌표에서 나올 수 있는 점수중에 가장 큰 점수를 출력해준다.

def search(x,y):
    queue = deque([(x,y,-1,graph[x][y])])
    max_score = 0
    for count in range(1,4):
        length = len(queue)
        for _ in range(length):
            nx,ny,prev_dir,score = queue.popleft()
            
            #ㅗ모양
            if ny == y + 2:
              
                if 0 <= nx-1 < n and 0 <= ny - 1 < m:
                    
                    max_score = max(max_score, score+graph[nx-1][ny-1])
                if 0 <= nx + 1 < n and 0 <= ny - 1 < m:
                    
                    max_score = max(max_score, score+graph[nx+1][ny-1])
               
            elif nx == x + 2:
               
                if 0 <= nx - 1 < n and 0 <= ny + 1 < m:
                    
                    max_score = max(max_score, score+graph[nx-1][ny+1])
                if 0 <= nx - 1 < n and 0 <= ny - 1 < m:
                   
                    max_score = max(max_score, score+graph[nx-1][ny-1])
                

            for i in range(4):
                if i != (prev_dir+2)%4 or prev_dir == -1:
                    current_x, current_y = nx + dx[i], ny + dy[i]
                    if 0 <= current_x < n and 0 <= current_y < m:
                        current_score = score + graph[current_x][current_y]
                        max_score = max(max_score, current_score)
                        queue.append((current_x,current_y,i,current_score))

    return max_score

해당 좌표의 최대 점수를 구하는 함수이다.

queue = deque([(x,y,-1,graph[x][y])])

queue에 시작점의 x좌표, y좌표, 전 방향, 해당 좌표의 점수를 추가해 준다.

여기서 전 방향을 저장하는 이유는 예를 들어, 시작점에서 밑 방향으로 움직였을 때 다음에 윗 방향으로 움직이면 제자리 걸음을 하게 되니 전에 있던 방향으로 움직이는 것을 막기 위해서이다.

for count in range(1,4):
        length = len(queue)
        for _ in range(length):
            nx,ny,prev_dir,score = queue.popleft()

각 칸마다 움직을 수 있는 모든 경우를 생각해야 한다.

	for i in range(4):
                if i != (prev_dir+2)%4 or prev_dir == -1:
                    current_x, current_y = nx + dx[i], ny + dy[i]
                    if 0 <= current_x < n and 0 <= current_y < m:
                        current_score = score + graph[current_x][current_y]
                        max_score = max(max_score, current_score)
                        queue.append((current_x,current_y,i,current_score))

4방향을 모두 탐색한다.

이 때 전에 움직였던 방향의 반대방향으로는 움직일 수 없다.

 

그런데, 이렇게만 하면 ㅏ,ㅓ,ㅗ,ㅜ 모양을 구할 수 없다.

ㅏ,ㅓ,ㅗ,ㅜ 모양을 따로 구해야 한다.

            if ny == y + 2:
              
                if 0 <= nx-1 < n and 0 <= ny - 1 < m:
                    # ㅗ 모양
                    max_score = max(max_score, score+graph[nx-1][ny-1])
                if 0 <= nx + 1 < n and 0 <= ny - 1 < m:
                    # ㅜ 모양
                    max_score = max(max_score, score+graph[nx+1][ny-1])
               
            elif nx == x + 2:
               
                if 0 <= nx - 1 < n and 0 <= ny + 1 < m:
                    # ㅏ 모양
                    max_score = max(max_score, score+graph[nx-1][ny+1])
                if 0 <= nx - 1 < n and 0 <= ny - 1 < m:
                    # ㅓ 모양
                    max_score = max(max_score, score+graph[nx-1][ny-1])

ny가 y+2일 경우는 오른쪽으로 2번 이동한 경우이기 때문에 ㅗ나 ㅜ가 나올 수 있다.

비슷하게 nx가 x+2일 경우는 밑으로 두 번 이동한 경우이기 때문에 ㅏ나 ㅓ가 나올 수 있다.

 

[전체 코드]

from collections import deque
n,m = map(int,input().split())
graph = [ list(map(int,input().split())) for _ in range(n)]

#방향
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

def search(x,y):
    queue = deque([(x,y,-1,graph[x][y])])
    max_score = 0
    for count in range(1,4):
        length = len(queue)
        for _ in range(length):
            nx,ny,prev_dir,score = queue.popleft()
            
            #ㅗ모양
            if ny == y + 2:
              
                if 0 <= nx-1 < n and 0 <= ny - 1 < m:
                    
                    max_score = max(max_score, score+graph[nx-1][ny-1])
                if 0 <= nx + 1 < n and 0 <= ny - 1 < m:
                    
                    max_score = max(max_score, score+graph[nx+1][ny-1])
               
            elif nx == x + 2:
               
                if 0 <= nx - 1 < n and 0 <= ny + 1 < m:
                    
                    max_score = max(max_score, score+graph[nx-1][ny+1])
                if 0 <= nx - 1 < n and 0 <= ny - 1 < m:
                   
                    max_score = max(max_score, score+graph[nx-1][ny-1])
                

            for i in range(4):
                if i != (prev_dir+2)%4 or prev_dir == -1:
                    current_x, current_y = nx + dx[i], ny + dy[i]
                    if 0 <= current_x < n and 0 <= current_y < m:
                        current_score = score + graph[current_x][current_y]
                        max_score = max(max_score, current_score)
                        queue.append((current_x,current_y,i,current_score))

    return max_score
    


result = 0

for i in range(n):
    for j in range(m):
        score = search(i,j)
        result = max(result, score)
print(result)

오랜만에 누군가의 도움없이 내 힘만으로 푼 문제였다.

매우 뿌듯하다😊