[python code review] 4주차(최단경로, 문자열 폭발, 뱀)

[최단경로] (하)

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

1753번: 최단경로

 

1. 구현

import heapq

def dijkstra(start):
    queue = []
    distance[start] = 0
    heapq.heappush(queue, (0, start))

    while queue:
        cost, now = heapq.heappop(queue)
        # 저장된 비용이 현재 비용보다 적다면 무시
        if cost > distance[now]:
            continue
        for next_cost, next_node in graph[now]:
            next_cost += cost
            if next_cost < distance[next_node]:
                distance[next_node] = next_cost
                heapq.heappush(queue, (next_cost, next_node))


v, e = map(int, input().split())
s = int(input())
graph = [[] for _ in range(v+1)]
distance = [1e9 for _ in range(v+1)]
for _ in range(e):
    a, b, c = map(int, input().split())
    # (비용, 도착노드) 저장
    graph[a].append((c, b))
dijkstra(s)
for i in range(1, v+1):
    if distance[i] == 1e9:
        print('INF')
    else:
        print(distance[i])

[문자열 폭발] (중)

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

9935번: 문자열 폭발

 

1. 구현

s, bomb = input(), input()
n, k = len(s), len(bomb)
result = ''
stack = []
for i in range(n):
    stack.append(s[i])
    # i번째 문자가 폭탄 문자열의 마지막 문자가 아닌 경우 무시
    if s[i] != bomb[-1]:
        continue
    # stack 상단에 폭탄 문자열이 있는지 검사
    data = ''.join(stack[-k:])
    if data != bomb:
        continue
    # 폭탄 문자열 제거
    for _ in range(k):
        stack.pop()
    # 폭탄 문자열 첫 글자가 등장하지 않을 때까지 저장 
    while stack:
        if stack[0] == bomb[0]:
            break
        result += stack.pop(0)

result += ''.join(stack)
if not result:
    result = 'FRULA'
print(result)

2. 코드 개선 

s, bomb = input(), input()
n, k = len(s), len(bomb)
result = ''
stack = []
for i in range(n):
    stack.append(s[i])
    # i번째 문자가 폭탄 문자열의 마지막 문자가 아닌 경우 무시
    if s[i] != bomb[-1]:
        continue
    # stack 상단에 폭탄 문자열이 있는지 검사
    data = ''.join(stack[-k:])
    if data != bomb:
        continue
    # 폭탄 문자열 제거
    for _ in range(k):
        stack.pop()

result += ''.join(stack)
if not result:
    result = 'FRULA'
print(result)

# 폭탄 문자열 첫 글자가 등장하지 않을 때까지 저장 
    while stack:
        if stack[0] == bomb[0]:
            break
        result += stack.pop(0)

처음 구현할 때 for 문 안에서 위 코드를 추가하여 폭탄 문자열이 아닌 문자들을 따로 result에 빼주고 for문 나와서 stack에 남아있는 문자열을 result에 저장하기 위해 result += ''.join(stack)를 넣었다. 그런데 생각해보니 굳이 따로 빼줄 필요없이 for문 밖에서 폭탄문자열이 아닌 문자를 마지막에 한번에 처리하면 됐다.  

 

[뱀] (상)

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

3190번: 뱀

 

1. 구현

from collections import deque
import sys
# 동 남 서 북
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def turn(check, d):
    # print('turned!')
    # 왼쪽으로 회전
    if d == 'L':
        if check == 0:
            return 3
        return check - 1
    # 오른쪽으로 회전
    else:
        if check == 3:
            return 0
        return check + 1

n = int(input())
board = [[0]*n for _ in range(n)]
k = int(input())
for _ in range(k):
    a, b = map(int, input().split())
    board[a-1][b-1] = 1
l = int(input())
table = [(input().split()) for _ in range(l)]
time = 1
# 뱀의 몸뚱아리 정보 때문에 bfs로 시작
def game():
    global time
    # print('game start')
    nx, ny = 0, 0
    que = deque([(nx, ny)])
    direction = 0
    board[nx][ny] = 2
    while True:
        nx, ny = nx + dx[direction], ny + dy[direction]
        if 0 > nx or nx >= n or 0 > ny or ny >= n:
            # print('벽에 닿아서 종료합니다')
            break
        if board[nx][ny] == 2:
            # print('뱀이 지 몸에 닿아 종료합니다')
            break
        # 사과 만나는 경우 아니면 꼬리 제거
        if board[nx][ny] != 1:
            xx, yy = que.popleft()
            board[xx][yy] = 0
        # 머리 붙이기
        board[nx][ny] = 2
        que.append((nx, ny))
        if table:
            if int(table[0][0]) == time:
                # print('방향을 회전해야 합니다...')
                t, d = table.pop(0)
                direction = turn(direction, d)
        time += 1

game()
print(time)

nx, ny = nx + dx[direction], ny + dy[direction]

이 부분을 nx, ny = x + dx[direction], y + dy[direction]와 같이 구현하여 처음에 실수가 있었다.

보통 bfs를 사용하는 경우, que에 (x, y) 좌표를 대입하고 상하좌우로 움직이며 벽이 아닌 좌표에 대해 특정 조건을 만족하면서 방문하지 않은 경우, 방문 처리와 동시에 que에 해당 좌표값을 넣어준다.

하지만 이 문제는 뱀의 위치 좌표를 que에 저장하고, 현재 좌표를 que에서 꺼내는 것이 아닌 방향 정보를 바탕으로 좌표를 설정해준다는 점에서 차이가 있다. 기본 방식대로 구현하면 현재 좌표 nx, ny에서 방금 전에 탐색한 좌표에는 접근할 수 있지만 (nx, ny = x - dx[direction], y - dy[direction]) 꼬리에 접근할 때 문제가 발생한다. 

 

시간, 방향 정보 저장할때 딕셔너리에 시간:방향으로 넣어준다면 다음과 같이 접근 가능   

for _ in range(int(input())):
    a, b = input().split()
    p[int(a)] = b 

 

if t in p.keys():
            time, d = t, p[t]
            direction = turn(direction, d)
            del p[time]