[python code review] 10주차 (공주님의 정원, 미네랄, 두 동전)

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

2457번: 공주님의 정원

[그리디]

- 월에 100을 곱하고 일을 더해서 날짜 형식을 변환하는 방식 참고 

- 또 다른 접근법 from datetime import date

                        date(2022, 3, 1).toordinal() # 738215   -> 1년 1월 1일을 기준으로 전체 일수 계산 

                        date(1,1,1).toordinal() # 1 

periods = []
answer = 0
n = int(input())

for _ in range(n):
    m1, d1, m2, d2 = map(int, input().split())
    periods.append((m1*100+d1, m2*100+d2))

periods.sort(key=lambda x:(x[0], x[1]))
wither_date = 301 # 꽃이 지는 날 저장
end = 0
while periods:
    # 꽃이 지는 날이 12월 1일을 넘거나 그 날에 더이상 필 꽃이 없는 경우
    if wither_date >= 1201 or wither_date < periods[0][0]:
        break

    for period in periods[:]:
        # 시작일 <= date <= 지는 날인 경우
        if wither_date >= period[0]:
            if end <= period[1]:
                end = period[1] # 꽃이 지는 날 저장
            periods.remove(period) # 배열에서 제거
        else:
            break

    answer += 1
    wither_date = end

print(0 if wither_date < 1201 else answer)

 

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

2933번: 미네랄

[BFS + 시뮬레이션]

1. 막대기를 제거한다. > throw 함수

2. 막대기를 제거한 곳에서 상하좌우로 검사하여 'x' 좌표일 때,

    해당 클러스터 덩어리가 공중에 떠있는지 검사하기 > new_cluster 함수

3. 공중에 떠있는 경우, 해당 클러스터의 맨 아래 행 부분의 좌표를 fall_lst에 저장

4. fall_lst에 저장된 좌표들에 for문을 돌려 몇칸이나 내려갈 수 있는지 k 변수로 체크 > fall 함수

from collections import deque


# 새롭게 분리된 클러스터가 있는지 검사
def new_cluster(x, y):
    # tmp = copy.deepcopy(caves)
    new_deq = deque([(x, y)])
    visited = [[False]*c for _ in range(r)]
    visited[x][y] = True
    fall_lst = []
  
    while new_deq:
        x, y = new_deq.popleft()
        # 바닥에 닿는 경우, return
        if x == r-1:
            return
        # 아래가 '.'인 경우, fall_lst 후보로 저장
        if caves[x+1][y] == '.':
            fall_lst.append([x, y])

        for dx, dy in moves:
            nx = x + dx
            ny = y + dy

            if not(0 <= nx < r and 0 <= ny < c):
                continue
            if caves[nx][ny] == 'x' and not visited[nx][ny]:
                visited[nx][ny] = True
                new_deq.append((nx, ny))

    fall(visited, fall_lst)


# 클러스터 위치 하향
def fall(visited, fall_list):
    k, flag = 1, 0

    while True:
        for i, j in fall_list:
            # 아래 행이 바닥인 경우
            if i + k == r - 1:
                flag = 1
                break
            # 아래 행이 'x'인 경우
            if caves[i + k + 1][j] == "x" and not visited[i + k + 1][j]:
                flag = 1
                break
        if flag:
            break
        k += 1

    for i in range(r - 2, -1, -1):
        for j in range(c):
            if caves[i][j] == 'x' and visited[i][j]:
                caves[i][j] = '.'
                caves[i + k][j] = 'x'


def throw(x, left):
    global deq
    y = 0
    # 왼쪽에서 던질 경우
    if left:
        for j in range(c):
            if caves[x][j] == 'x':
                caves[x][j] = '.'
                y = j
                break
    # 오른쪽에서 던질 경우
    else:
        for j in range(c - 1, -1, -1):
            if caves[x][j] == 'x':
                caves[x][j] = '.'
                y = j
                break

    # 막대기가 날아간 좌표의 상하좌우 > 'x' 검사
    for dx, dy in moves:
        nx = dx + x
        ny = dy + y

        if 0 <= nx < r and 0 <= ny < c:
            if caves[nx][ny] == 'x':
                deq.append((nx, ny))


r, c = map(int, input().split())
caves = [list(input()) for _ in range(r)]
n = int(input())
heights = list(map(int, input().split()))
direction = True
moves = [(1, 0), (0, 1), (0, -1), (-1, 0)]
deq = deque()

for i in range(n):
    x = r - heights[i]
    # 막대기 던지기
    throw(x, direction)

    while deq:
        x, y = deq.popleft()
        new_cluster(x, y)

    # 던지는 방향 좌우 회전
    direction = not direction

for i in range(r):
    print(''.join(caves[i]))

 

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

16197번: 두 동전

[BFS]

두 좌표 방문처리시 dictionary 사용 >

좌표 문자열을 key로 저장하여 시간복잡도 O(1) 처리    

from collections import deque

def bfs(x1, y1, x2, y2):
    global dropped
    deq = deque([(1, x1, y1, x2, y2)])
    visit = {} # 딕셔너리를 이용한 방문 처리
    s = str(x1) + str(y1) + str(x2) + str(y2)
    visit[s] = 1
    while deq:
        total, x1, y1, x2, y2 = deq.popleft()
        if total > 10:
            return -1

        for dx, dy in moves:
            dropped = 0
            next_x1, next_y1 = move(dx, dy, x1, y1)
            next_x2, next_y2 = move(dx, dy, x2, y2)
            if dropped == 2: # 코인 2개가 떨어진 경우
                continue
            if dropped == 1:
                return total # 코인 1개가 떨어진 경우
            
            s = str(next_x1) + str(next_y1) + str(next_x2) + str(next_y2)
            if not visit.get(s, 0):
                visit[s] = 1
                deq.append((total+1, next_x1, next_y1, next_x2, next_y2))

    return -1


def move(dx, dy, x, y):
    global dropped

    nx = dx + x
    ny = dy + y
    if not (0 <= nx < n and 0 <= ny < m): # board 밖으로 떨어지는 경우
        dropped += 1
        return [-1, -1]
    if board[nx][ny] == '#': # 벽인 경우 제자리 
        return [x, y]

    return [nx, ny] # 이동 가능한 경우 


moves = [(1,0),(0,1),(0,-1),(-1,0)]
n, m = map(int, input().split())
dropped = 0 # 코인이 떨어지는 개수 
board, coins = [], []
for i in range(n):
    board.append(input())
    for j in range(m):
        if board[i][j] == 'o': # 코인 좌표 저장
                coins.append((i, j))

print(bfs(coins[0][0], coins[0][1], coins[1][0], coins[1][1]))

방문 처리하는 visit 배열을 제거해도 통과되었지만 visit 배열을 사용할 경우 훨씬 더 많은 메모리와 시간이 절약됐다.