[파이썬] 백준 5213 : 과외맨 (골드2)

[파이썬] 백준 5213 : 과외맨 (골드2)

5213번: 과외맨

---

문제

---

풀이

0. 방향성 생각

• 타일 넘버링을 잘 하기.
• 역추적을 해야한다.역추적 배열을 하나 더 만들어서 새로 갱신하는 경우에 온 경로에 이전 좌표를 갱신.

1. array 만들기

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

arr = []
n = int(input())
for h in range(n):
    row = []
    if not h%2:
        for _ in range(n) : row.extend(list(map(int,input().split())))
    else:
        for _ in range(n-1) : row.extend(list(map(int,input().split())))
        row = [0]+row+[0]
    arr.append(row)

• 배열 받아주기

2. tile 넘버링

tile = [[-1]*2*n for _ in range(n)]
count = 1
for h in range(n):
    temp = 0
    for w in range(2*n):
        if h%2 and (w==0 or w==2*n-1):
            continue
        else :
            tile[h][w] = count
            temp += 1
            
        if temp==2:
            count += 1
            temp = 0

• 타일넘버링 규칙은 문제에 서술돼있으니 자세한 설명은 생략한다.
• 사실 위에 arr이랑 한 for문으로 구성할 수도 있는데, 고치기 귀찮아서 패스.

3. visit, trace 배열 생성

dire = [(1,0),(0,1),(-1,0),(0,-1)]
inf = 1e6
visit = [[inf]*2*n for _ in range(n)]
visit[0][0] = 1

trace = [[(-1,-1)]*2*n for _ in range(n)]
trace[0][0] = (0,0)

• 배열을 생성하고 시작점 초기화해주기.

4. BFS

max_tile,max_tile_loc = -1,(0,0)
q = deque([(0,0)])
while q:
    x,y = q.popleft()
    t = visit[y][x]
    
    for dx,dy in dire:
        nx,ny = x+dx,y+dy
        
        if 0<=nx<2*n and 0<=ny<n:
            if tile[y][x] == tile[ny][nx] and t < visit[ny][nx]:
                q.append((nx,ny))
                visit[ny][nx] = t
                trace[ny][nx] = (x,y)
                if max_tile < tile[ny][nx]:
                    max_tile = tile[ny][nx]
                    max_tile_loc = (nx,ny)
            else :
                if arr[y][x] == arr[ny][nx] and t+1 < visit[ny][nx]:
                    q.append((nx,ny))
                    visit[ny][nx] = t+1
                    trace[ny][nx] = (x,y)
                    if max_tile < tile[ny][nx]:
                        max_tile = tile[ny][nx]
                        max_tile_loc = (nx,ny)

• 가장 멀리 도달한 타일을 찾기 위해서 max_tile과 그 좌표 loc를 기록한다. (사실 시간초과나서 이 부분을 추가했었는데 다른 부분 수정하면서 없어짐. 큰 차이 없을듯?)
• 타일이 같은 경우에는 새로 갱신하는 경우에 넣어준다.
• 타일이 같지 않은 경우에는 인접 숫자가 같고 새로 갱신하는 경우에 넣어준다.
• 갱신하면서 max_tile과 좌표 기록하기

5. 경로 추적

def path(a,b):
    ans = [tile[b][a]]
    x,y = trace[b][a]
    while True:
        if tile[y][x] == 1:
            ans.append(tile[y][x])
            break
        if tile[y][x] != ans[-1]:
            ans.append(tile[y][x])
        x,y = trace[y][x]
    return ans[::-1]

a,b = max_tile_loc
answer = path(a,b)
print(len(answer))
print(*answer)

• 1번 타일이 나올 때 까지 경로 추적해주기. 재귀로 풀 수도 있지만 그냥 진행.
• 같은 타일인 경우에는 추가하지 않는다.

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

arr = []
n = int(input())
for h in range(n):
    row = []
    if not h%2:
        for _ in range(n) : row.extend(list(map(int,input().split())))
    else:
        for _ in range(n-1) : row.extend(list(map(int,input().split())))
        row = [0]+row+[0]
    arr.append(row)

tile = [[-1]*2*n for _ in range(n)]
count = 1
for h in range(n):
    temp = 0
    for w in range(2*n):
        if h%2 and (w==0 or w==2*n-1):
            continue
        else :
            tile[h][w] = count
            temp += 1
            
        if temp==2:
            count += 1
            temp = 0

dire = [(1,0),(0,1),(-1,0),(0,-1)]
inf = 1e6
visit = [[1e9]*2*n for _ in range(n)]
visit[0][0] = 1

trace = [[(-1,-1)]*2*n for _ in range(n)]
trace[0][0] = (0,0)

max_tile,max_tile_loc = -1,(0,0)
q = deque([(0,0)])
while q:
    x,y = q.popleft()
    t = visit[y][x]
    
    for dx,dy in dire:
        nx,ny = x+dx,y+dy
        
        if 0<=nx<2*n and 0<=ny<n:
            if tile[y][x] == tile[ny][nx] and t < visit[ny][nx]:
                q.append((nx,ny))
                visit[ny][nx] = t
                trace[ny][nx] = (x,y)
                if max_tile < tile[ny][nx]:
                    max_tile = tile[ny][nx]
                    max_tile_loc = (nx,ny)
            else :
                if arr[y][x] == arr[ny][nx] and t+1 < visit[ny][nx]:
                    q.append((nx,ny))
                    visit[ny][nx] = t+1
                    trace[ny][nx] = (x,y)
                    if max_tile < tile[ny][nx]:
                        max_tile = tile[ny][nx]
                        max_tile_loc = (nx,ny)

def path(a,b):
    ans = [tile[b][a]]
    x,y = trace[b][a]
    while True:
        if tile[y][x] == 1:
            ans.append(tile[y][x])
            break
        if tile[y][x] != ans[-1]:
            ans.append(tile[y][x])
        x,y = trace[y][x]
    return ans[::-1]

a,b = max_tile_loc
answer = path(a,b)
print(len(answer))
print(*answer)

 

코멘트

이전에 못풀었던 문제. 디버깅해서 풀었다.

공부를 좀 하고 보니까 코드도 비효율적으로 짠 부분이 많아서 살짝 수정.

최적화가 좀 덜돼서 시간초과가 몇 번 발생했지만, 플레 문제나 다른 효율성 위주 문제에서 최적화 하는 발상이 도움이 돼서 금방 풀었다.