BAEKJOON 14500

29 Apr 2020

문제

입력

---

나의 처음 코드

문제를 읽어보면, 정사각형 4개를 이어붙인 모양을 테트로미노라고 하고, 우리는 네개로 둘러싸인 면적에 있는 숫자들의 합중에 최대값을 구해야 한다. 여기까지만 읽으면? dfs문제인것 같기도 하고 bfs문제인것 같기도하고,,
그래서 나는 처음에 bfs와 dfs합쳐진 방식으로 풀다가 중간에 안된다는 것을 느끼고 다 삭제하고 다시 코드를 짰다. 내가 작성한 코드는 dfs형식에 백트래킹 방식을 더했고, 기존의 dfs는 다음 좌표로 가고 또 다음 좌표로 가고를 반복했지만, 여기서는 ㅗ 모양의 형식도 신경써줘야 하므로 자기 자신을 한번더 dfs로 참조하는 방식을 썼다. 그리고 빅오를 줄이기 위해 제일 큰 숫자가 포함이 되도록 딕셔너리를 짜서, 큰 숫자들 위주로 dfs를 진행했다. 사실상 주어진 맵에서 나올 수 있는 최대값이 나오지 않는다면, 브루트 포스느낌으로 다 둘러보는 느낌이다. (사실상 의미 없다는 뜻) 코드는 다음과 같다.

N, M = list(map(int, input().split()))
map_list = [[0] * M for _ in range(N)]
visited_list = [[0] * M for _ in range(N)]
map_dict = {}
#map 만들기
for i in range(N):
    tmp_list = list(map(int, input().split()))
    for j in range(M):
        map_list[i][j] = tmp_list[j]
        if tmp_list[j] not in map_dict:
            map_dict[tmp_list[j]] = [(i, j, tmp_list[j])]
        else:
            map_dict[tmp_list[j]].append((i, j, tmp_list[j]))            
#딕셔너리 리스트화
map_dict_list = list(sorted(map_dict.items(), key = lambda x : -x[0]))

max_sum = 0 #이 문제에서 가질 수 있는 최대값
real_sum = -1 #매 수행마다 저장할 최대값
tmp_count = 0 #4칸먹는거 세는 변수
#좌표 이동 리스트
ud_list = [0, 0, 1, -1]
rl_list = [1, -1, 0, 0]

#dfs로 수행
def solution(x, y, count, m_sum):
    global max_sum, real_sum
    #4회를 진행했을 경우
    if count == 3:
        if m_sum == max_sum:
            real_sum = m_sum
        else:
            real_sum = m_sum if real_sum < m_sum else real_sum
        return
    
    for i in range(4):
        tmp_x = x + ud_list[i]
        tmp_y = y + rl_list[i]
        
        if 0 <= tmp_x < N and 0 <= tmp_y < M and visited_list[tmp_x][tmp_y] == 0:
            #방문 표시, 누적값 더해주기
            visited_list[tmp_x][tmp_y] = 1
            m_sum += map_list[tmp_x][tmp_y]
            #칸을 넘어가지말고, 다음칸 수행후에도 내 칸에서 갈 수 있는 곳 찾기
            solution(x, y, count + 1, m_sum)
            #다음 칸에서 dfs하기
            solution(tmp_x, tmp_y, count + 1, m_sum)
            #방문 표시 해제, 누적값 빼주기
            m_sum -= map_list[tmp_x][tmp_y]
            visited_list[tmp_x][tmp_y] = 0

#나올 수 있는 최대값 구하기, real_sum 값
for info in map_dict_list:
    if tmp_count == 4:
        break
    val = info[0]
    length = len(info[1])
    for _ in range(length):
        if tmp_count == 4:
            break
        tmp_count += 1
        max_sum += val


#최대값으로 정렬된 딕셔너리 리스트를 최대값부터 순회해주기.
for info in map_dict_list:
    coord_list = info[1] #(i, j, sum)
    for coord in coord_list:
        #본인 좌표 방문 표시
        visited_list[coord[0]][coord[1]] = 1
        solution(coord[0], coord[1], 0, coord[2])
        #본인 좌표 방문 표시 해제
        visited_list[coord[0]][coord[1]] = 0
        
        
print(real_sum)

Python3에서는 시간초과가 뜨지만, pypy3에서는 아슬아슬하게 통과한다. 다른 사람들의 풀이를 보니, 모양별로 좌표를 만들어줘서 ud_list, rl_list처럼 더해주면서 값의 validity를 확인하고 면적에 있는 합을 구하는 식으로 했다. 그러니, 시간이 짧게 나올 수 밖에,,,, 이러한 방법도 있더라라고 알아두기만 하자,,,
실수를 하지 않도록 항상 주의해서 문제를 풀도록 하자,,,, 화이팅,,,