[백준]230403-09 문제풀이(Python)

9328. 열쇠

from collections import deque
import sys
input = sys.stdin.readline

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

def bfs(y, x):
    global ans
    q = deque()
    q.append((y, x))
    visited = [[False] * (w + 2) for _ in range(h + 2)]
    visited[y][x] = True
    while q:
        cnt = 0
        now = q.popleft()
        for d in range(4):
            ny, nx = now[0] + dy[d], now[1] + dx[d]
            if ny < 0 or ny > h + 1 or nx < 0 or nx > w + 1: continue
            if lst[ny][nx] == '*': continue
            if visited[ny][nx]: continue
            if lst[ny][nx] == '$':
                ans += 1
                lst[ny][nx] = '.'
                visited[ny][nx] = True
                q.appendleft((ny, nx))
                cnt = 0
            if lst[ny][nx] == '.':
                visited[ny][nx] = True
                q.appendleft((ny, nx))
                cnt = 0
            if lst[ny][nx].isalpha():
                if ord(lst[ny][nx]) in range(97, 123):
                    key.append(lst[ny][nx])
                    lst[ny][nx] = '.'
                    visited = [[False] * (w + 2) for _ in range(h + 2)]
                    visited[ny][nx] = True
                    q.appendleft((ny, nx))
                    cnt = 0
                if ord(lst[ny][nx]) in range(65, 91):
                    if lst[ny][nx].lower() in key:
                        key.append(lst[ny][nx])
                        lst[ny][nx] = '.'
                        visited[ny][nx] = True
                        q.appendleft((ny, nx))
                        cnt = 0
                    else:
                        q.append((y, x))
                        cnt += 1

        if cnt > len(q):
            return

T = int(input())
for tc in range(T):
    h, w = map(int, input().split())
    lst = [['.'] * (w + 2)] + [['.'] + list(input().strip()) + ['.'] for _ in range(h)] + [['.'] * (w + 2)]
    key = list(input().strip())
    ans = 0
    bfs(0, 0)
    print(ans)

하나하나 예외를 지정해줘가면서 가고싶은 길의 우선순위에 따라 append와 appendleft를 적절히 섞어가면서 bfs로 구현했다. 뭔가 되게 효율적으로 풀었다 생각했는데 set도 안쓰고 글자도 아스키코드 하나씩 찾아가면서 한게 시간을 남보다 몇배는 잡아먹게 한 원인이 아닌가 싶다. 일단 맞았긴 한데, 실제로 코테에서 최적화 할 시간이 없다고 하면 낭패일 것 같은 상황. 항상 문제 푸는데 혈안이 돼서 최적화는 뒷전이 되는 것 같다. 요런 디테일을 좀 잘 챙겨주면 좋을텐데...

14500. 테트로미노

import sys
input = sys.stdin.readline

def tetromino(y, x):
    global ans

    for t in range(7):
        for pm in [-1, 1]:
            for yx in [0, 1]:
                SUM = 0
                for d in range(4):
                    ny, nx = y + pm*tetris[t][yx][d], x + pm*tetris[t][1-yx][d]
                    if ny < 0 or ny > N - 1 or nx < 0 or nx > M - 1:
                        break
                    SUM += lst[ny][nx]
                ans = max(SUM, ans)

tetris = [[[0, 0, 0, 0], [0, 1, 2, 3]], [[0, 0, 1, 1], [0, 1, 0, 1]],
    [[0, 0, 0, -1], [0, 1, 2, 2]], [[0, 0, 0, 1], [0, 1, 2, 2]],
    [[0, 0, -1, -1], [0, 1, 1, 2]], [[0, 0, 1, 1], [0, 1, 1, 2]],
    [[0, -1, 0, 0], [0, 1, 1, 2]]]

N, M = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(N)]
ans = 0

for i in range(N):
    for j in range(M):
        tetromino(i, j)

print(ans)

LG 코테 기출이라 해서 풀어봤다. 첨부터 코드를 짧게 할 생각으로 for문을 4중으로 쓰더라도 이쁘게 해보려고 했다. 적당한 시간에 적당한 풀이로 잘 푼 것 같은데 코테에서 긴장해서 이런 문제 틀리지만 않았으면 좋겠다 ㅠㅠ

20311. 화학 실험

import sys
input = sys.stdin.readline
import heapq

N, K = map(int, input().split())
inp = list(map(int, input().split()))
idx = [i for i in range(1, K + 1)]
lst = [[-inp[i], idx[i]] for i in range(K)]
heapq.heapify(lst)
ans = []

while lst:
    if len(lst) == 1:
        if not ans and lst[0][0] == -1:
            ans = [1]
            break
        if lst[0][0] < -1 or lst[0][1] == ans[-1]:
            ans = [-1]
            break
        ans.append(lst[-1][1])
        lst.pop()
    else:
        now = heapq.heappop(lst)
        if ans and now[1] == ans[-1]:
            temp = heapq.heappop(lst)
            now, temp = temp, now
            heapq.heappush(lst, temp)
        ans.append(now[1])
        now[0] += 1
        if not now[0]:
            continue
        heapq.heappush(lst, now)

print(*ans)

처음 풀어본 서브태스크 문제. 인데 서브태스크고 나발이고 엣지 케이스 못찾아서 한참을 헤맸다. 첨엔 dfs로 했다가 deque로 했다가 최대힙을 써야하는 걸 깨닫고 구현을 어케어케 했는데 생각나는 엣지케이스는 해도 안풀리고 결국 근성으로 찾아내긴 했다. 엣지케이스에 강한 로직을 짤 줄 알아야 하는데 너무 일반 테케에 초점을 두고 생각하는게 문제인 것 같다. 아래는 내가 힘겨웠던 반례들

#1
3 2
1 2
답: 2 1 2

#2
1 1
1
답: 1

 

토욜에 시험도 있었고 코테랑 면접 계획도 짜고 자바공부 DB공부 플젝 하느라 정신이 너무 없다. 일단 이번주는 다른건 미뤄두고 코테나 빡세게 준비해볼까 한다...