Enochkon's blog

문제

코드

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

n,m=map(int,input().split())
arr = []
check= [[[0,0,0] for _ in range(m)] for _ in range(n)]
d=[(1,0,'b'),(1,-1,'l'),(1,1,'r')]
q=deque()

for i in range(n):
    arr.append(list(map(int,input().split())))

for i in range(n):
    for j in range(m):
        count=0
        if(i==0):
            check[i][j][0]=check[i][j][1]=check[i][j][2]=arr[i][j]
            continue
        if(i==1):
            if j==0:
                check[i][j][0]=float("inf")
                check[i][j][1]=arr[i][j]+arr[i-1][j]
                check[i][j][2]=arr[i][j]+arr[i-1][j+1]
            elif j==m-1:
                check[i][j][2]=float("inf")
                check[i][j][0]=arr[i][j] + arr[i-1][j-1]
                check[i][j][1]=arr[i][j] + arr[i-1][j]
            else:
                check[i][j][2]=arr[i][j] + arr[i-1][j+1]
                check[i][j][0]=arr[i][j] + arr[i-1][j-1]
                check[i][j][1]=arr[i][j] + arr[i-1][j]
            continue
        if j==0:
            check[i][j][0]=float("inf")
            check[i][j][1]=arr[i][j] + check[i-1][j][2]
            check[i][j][2]=arr[i][j] + min(check[i-1][j+1][0],check[i-1][j+1][1])
        elif j==m-1:
            check[i][j][0]=arr[i][j] + min(check[i-1][j-1][1],check[i-1][j-1][2])
            check[i][j][1]=arr[i][j] + check[i-1][j][0]
            check[i][j][2]=float("inf")
        else:
            check[i][j][0]=arr[i][j] + min(check[i-1][j-1][1],check[i-1][j-1][2])
            check[i][j][1]=arr[i][j] + min(check[i-1][j][0],check[i-1][j][2])
            check[i][j][2]=arr[i][j] + min(check[i-1][j+1][0],check[i-1][j+1][1])

res=float("inf")
for i in range(m):
    res=min(min(check[n-1][i]),res)
print(res)

풀이

• 최소 비용의 경로 찾기

1. 각각의 경로에 드는 연료의 양을 입력받고, 누적 연료를 입력할 check 배열을 추가해준다.
   1. check[i][j][l] : i는 열, j는 행 그리고 l은 바로 전 경로가 어디서 왔는지를 나타낸다
   • l에서 0은 왼쪽 위에서 내려온것, 1은 바로 위에서 내려온것, 2는 오른쪽 위에서 내려온것 이다.
2. 첫번째 구역부터 반복문으로 탐색해준다.
   1. 제일 첫번째인 i==0인 곳은 그 구역 연료의 양을 추가해준다
   2. 두번째인 i==1은 바로 위와 현재 경로만 생각해주면 되므로 각각의 값을 추가해준다.
   3. 그 뒤부터는 최소 연료양의 경로를 추가해준다. 단, 같은 방향이 연속되면 안되기 때문에 방향을 생각해서 계산한다.

우선 각각의 방향에서 온 값을 계산한다
1. 왼쪽에서 내려온 경우 (l==0) check[i][j][0]일때는 왼쪽으로 두번 연속으로 내려오면 안되므로 오른쪽, 왼쪽 으로 내려왔거나 아래 왼쪽으로 내려온 경우만 생각해주면 된다.
즉 arr[i][j] + min(check[i-1][j-1][1],check[i-1][j-1][2])
현재의 값 + (check[i-1][j-1][1] 아래로 내려온 후 왼쪽에서 온 경우와, check[i-1][j-1][2] 오른쪽에서 내려온 후 왼쪽에서 내려온 경우 중 작은 값은 넣어준다.)

2. 바로 아래로 내려온 경우 (l==1)
arr[i][j] + arr[i][j] + min(check[i-1][j][0],check[i-1][j][2])
현재의 값 + (check[i-1][j][0] 왼쪽에서 내려온 후 아래로 내려온 경우와, check[i-1][j][2] 오른쪽에서 내려온 후 아래로 내려온 경우 중 작은 값은 넣어준다.)

3. 오른쪽에서 아래로 내려온 경우 (l==2)
arr[i][j] + min(check[i-1][j+1][0],check[i-1][j+1][1])
현재의 값 + (check[i-1][j+1][0] 왼쪽에서 내려온 후 오른쪽으로 내려온 경우와, check[i-1][j+1][1] 바로 아래로 내려온 후 오른쪽에서 내려온 경우 중 작은 값은 넣어준다.)

→ 이 조건을 만족한 후 제일 마지막 행에서 제일 작은 값을 찾아서 출력한다.

특이사항

• 유사문제 17484에서는 bfs로 풀었지만 이번에는 그럴경우 시간초과가 난다. DP로 풀어야 하는문제
• 기본적으로 세 방향에서 내려온 값들을 찾지만, 범위를 벗어나거나 하는 경우에는 inf를 넣어줘서 없는 경로라는 것을 표시한다

문제

코드

from collections import deque

n,m=map(int,input().split())
arr = []
check= [[0 for _ in range(m)] for _ in range(n)]
d=[(1,0,'b'),(1,-1,'l'),(1,1,'r')]
q=deque()

for i in range(n):
    arr.append(list(map(int,input().split())))

for i in range(m):
    q.append((0,i,arr[0][i],'0'))
    while len(q)>0:
        ci,cj,count,direction=q.popleft()
        if check[ci][cj]==0 or check[ci][cj]>count:
            check[ci][cj]=count
        for a,b,c in d:
            if(c==direction):
                continue
            ni=ci+a
            nj=cj+b
            if(0<=ni<n and 0<=nj<m):
                q.append((ni,nj,count+arr[ni][nj],c))
print(min(check[n-1]))

풀이

• 위부터 아래로 내려갈때에 연료를 최소로 사용하는 경로를 찾아라

1. 각 경로의 연로를 입력 받고, 새로운 check 배열을 생성한다.
2. 출발지점들을 q에 넣고, bfs를 돌리며 아래로 나아간다.
   1. 같은방향으로 두번 가지 않게 ‘l’, ‘b’, ‘r’로 구분해서 체크한다.
   2. 만약 현재 위치의 check배열이 0이거나 현재 count보다 크면 count를 넣어준다
3. bfs를 전부 돌린 후 경로의 제일 끝 부분중 최소값을 출력한다.

문제

코드

from collections import deque 

def solution(board):
    answer = 0
    board = [list(_) for _ in board]
    row, col = len(board), len(board[0])
    res = [[0 for i in range(len(board[0]))] for j in range(len(board))]
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    q = deque()
    
    def slide(i,j,dr,dc):
        while True:
            ci,cj = i + dr, j + dc
            if not (0 <= ci < row and 0 <= cj < col) or board[ci][cj] == 'D':
                return ci-dr, cj-dc
            i,j=ci,cj
                
    for i in range(row):
        for j in range(col):
            if board[i][j]== 'R':
                q.append((i,j,0))
    while q:
        cx, cy, dist = q.popleft()
        res[cx][cy]=dist
        if(board[cx][cy]=='G'):
            answer=dist
            break
        for dr , dc in d:
            nx,ny=slide(cx,cy,dr,dc)
            if(res[nx][ny]==0):
                res[nx][ny]=1
                q.append((nx,ny,dist+1))
    
    if(answer==0):
        return -1
    else:
        return answer

풀이

• 리코쳇 로봇 최소 경로 찾기

1. 문자열을 리스트화 시켜준다.
2. 시작지점 R 부터 목적지 G 지점까지 도달하는 경로를 찾는다.
   1. BFS를 사용한다.
   2. 한칸씩 이동시키는 것이 아닌 slide 함수를 사용해서 진행방향에 벽 혹은 끝까지 진행하는 좌표를 얻는다.
   3. 해당 좌표를 지나간적이 없으면 q에 추가해준다.
   4. 만약 현재 좌표가 ‘G’면 answer에 거리를 추가한다
3. 모든 탐색이 끝난 후 answer이 0인 경우에는 경로를 못찾은것이기 때문에 -1을 아니면 answer을 출력한다.

문제

코드

from collections import deque 

def solution(maps):
    maps = [list(_) for _ in maps]
    rows, cols = len(maps), len(maps[0])
    distance = [[-1 for _ in range(cols)] for _ in range(rows)]
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    q = deque()
    
    for i in range(rows):
        for j in range(cols):
            if maps[i][j] == 'L':
                q.append((i, j, 0))
                distance[i][j] = 0
    while q:
        cx, cy, dist = q.popleft()
        
        for dx, dy in d:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < rows and 0 <= ny < cols and maps[nx][ny] != 'X' and distance[nx][ny] == -1:
                distance[nx][ny] = dist + 1
                q.append((nx, ny, dist + 1))
                
    l_dist, e_dist = -1, -1
    for i in range(rows):
        for j in range(cols):
            if maps[i][j] == 'S' and l_dist == -1:
                l_dist = distance[i][j]
            if maps[i][j] == 'E':
                e_dist = distance[i][j]
    
    if l_dist == -1 or e_dist == -1:
        return -1
    else:
        return l_dist + e_dist

풀이

• 시작지점부터 레버까지, 그리고 레버부터 탈출지점까지의 거리를 구해라

1. 입력받은 문자열을 리스트형태로 변환
2. 거리를 입력할 배열 구현
3. 시작지점부터 바로 탈출지점까지 가는게 아닌 중간에 레버를 올려야하므로 레버를 기준으로 시작지점과 탈출지점의 최단거리를 구하면 된다고 생각
   1. bfs를 활용해 레버의 위치인 ‘L’부터 시작, 전체 미로의 거리를 L을 기준으로 기입
   2. 거리를 입력한 distance 배열에서 시작지점인 S와 탈출지점인 E의 좌표에 대한 거리의 합을 출력
   3. 만약 하나라도 -1인 경우 길이 없는것이므로 -1 출력

특이사항

• 출발 지점부터 레버까지와 레버부터 도착 지점까지의 길이 중복되도 된다길래 어떻게 구현해야할지 생각하다가, 두번의 bfs를 돌리면 되겠다고 생각했다. → 하지만 이렇게 구현할 경우 낭비가 심하다고 생각. → 중간 지점인 레버를 기준으로 거리를 구하면 bfs를 한번만 돌릴 수 있다고 생각 후 구현

문제

코드

from collections import deque

def solution(s):
    q = deque()
    for i in range(len(s)):
        if(len(q)==0 or s[i]!=q[len(q)-1]):
            q.append(s[i])
        elif(s[i]==q[len(q)-1]):
            q.pop()
    return 1 if len(q)==0 else 0

풀이

• 문자열에서 연속으로 오는 문자를 제거할 때 전부 제거할 수 있는지를 확인한다.
• 스택의 개념을 사용하면 손쉽게 풀 수 있음

1. 스택 역할을 해주기 위해 deque 선언
2. s문자열을 for문으로 돌면서 문자 제거
   1. q가 비어있거나 q의 마지막 문자와 현재의 문자가 다르면 q에 넣어준다.
   2. 만약 q의 마지막 문자와 현재 문자가 같으면 q를 pop해준다.
3. 마지막에 q가 비어있을 경우 1을 아닐경우 0을 출력한다.

문제

코드

import sys
from functools import cmp_to_key

input = sys.stdin.readline

def cmpDic(a,b):
    if(a[1]<b[1]):
        return 1
    elif (a[1]>b[1]):
        return -1
    if(len(a[0])<len(b[0])):
        return 1
    elif(len(a[0])>len(b[0])):
        return -1
    if a>b:
        return 1
    else:
        return -1

N, M= map(int,input().split())
res={}
for i in range(N):
    a=input().rstrip()
    if(len(a)<M):
        continue
    if(a in res):
        res[a]+=1
    else:
        res[a]=1
res = [(k, v) for k, v in res.items()]

res.sort(key=cmp_to_key(cmpDic))
for i,j in res:
    print(i)

풀이

• 영단어들을 조건에 맞게 정렬시킨다.

1. N,M을 입력받는다.
2. N개의 단어를 받으면서 길이가 M 이상인 단어들만 res에 넣어준다.
   1. res는 딕셔너리를 사용해서 여러번 나온 단어들은 +1씩 해준다.
3. 입력받은 단어들을 (key, value)의 튜플로 이루어진 리스트로 변환한다.
4. 변환한 리스트를 조건에 맞게 정렬한다
   1. 자주 나오는 단어일수록 앞에 배치한다.
   2. 해당 단어의 길이가 길수록 앞에 배치한다.
   3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다
5. 정렬한 res를 출력한다.

문제

코드

from functools import cmp_to_key

def cmpFile(a,b):
    if a[0].upper() > b[0].upper():
        return 1
    elif a[0].upper() < b[0].upper():
        return -1
    else:
        if int(a[1]) > int(b[1]):
            return 1
        elif int(a[1]) < int(b[1]):
            return -1
    return 0

def solution(files):
    answer = []
    res=[]
    for i in files:
        head=0
        number=0
        for j in range(len(i)):
            if head==0 and '0'<=i[j]<='9':
                head=j
            if head!=0 and number==0 and ('0'>i[j] or i[j]>'9'):
                number=j
        if(number==0):
            number=len(i)
        answer.append([i[:head],i[head:number],i[number:]])
    answer.sort(key=cmp_to_key(cmpFile))
    
    for head,number,tail in answer:
        res.append(head+number+tail)
    return res

풀이

• 파일명을 특정 기준을 따라 정렬해라

1. head, number, tail 구역으로 나눈다.
2. 나눈 파일명을 기준에 따라 정렬하기 위해 cmpFile함수를 작성하고 cmp_to_key를 사용해서 비교함수로 사용한다
3. 정렬한 파일명을 다시 합쳐서 리턴한다.

특이사항

• 람다와 정규식을 사용해서 풀면 이정도로 줄일 수 있단다…

import re

def solution(files):
    a = sorted(files, key=lambda file : int(re.findall('\\d+', file)[0]))
    b = sorted(a, key=lambda file : re.split('\\d+', file.lower())[0])
    return b

• 이게 파이썬이지…

문제

코드

import sys
sys.setrecursionlimit(1000000)

def dfs(land, i, j, m, n, check, patch_id):
    if i < 0 or i >= m or j < 0 or j >= n or check[i][j] != 0 or land[i][j] == 0:
        return 0
    check[i][j] = patch_id 
    size = 1  
    
    size += dfs(land, i + 1, j, m, n, check, patch_id)
    size += dfs(land, i - 1, j, m, n, check, patch_id)
    size += dfs(land, i, j + 1, m, n, check, patch_id)
    size += dfs(land, i, j - 1, m, n, check, patch_id)

    return size

def solution(land):
    m = len(land)
    n = len(land[0])
    check = [[0] * n for _ in range(m)]

    patch_sizes = {}
    patch_id = 1

    for i in range(m):
        for j in range(n):
            if land[i][j] == 1 and check[i][j] == 0:
                patch_size = dfs(land, i, j, m, n, check, patch_id)
                patch_sizes[patch_id] = patch_size
                patch_id += 1

    max_oil = 0
    for j in range(n):
        oil_in_column = set()
        for i in range(m):
            if check[i][j] != 0:
                oil_in_column.add(check[i][j])

        total_oil = sum(patch_sizes[pid] for pid in oil_in_column)
        max_oil = max(max_oil, total_oil)

    return max_oil

풀이

• 일자로 팠을 때 석유를 최대한 많이 얻는 경우는?

1. 우선 땅에 있는 모든 석유 웅덩이를 dfs로 확인하여 1,2,3 라벨과 넓이를 붙여준다.
2. 그 뒤 땅을 한번씩 돌면서 일자로 팠을 때 시추 가능한 양을 체크하면서 최대로 시추 가능한 곳의 양을 max_oil에 저장하고 리턴한다.

특이사항

• 우선 정확성은 전부 통과했는데 효율성에러 런타임 에러가 나서 왜그런가 하고 생각해봤는데, 파이썬의 재귀 제한 때문에 오류가 나는것을 파악해서 재귀 허용을 늘려주면 통과한다. (기본 재귀 1000번)
• import sys sys.setrecursionlimit(1000000)
• 원래는 매 시행때 dfs를 돌면서 계속 체크를 하려고 했다가 그렇게 되면 효율성을 통과하지 못할거라고 생각하고 미리 dfs로 모든 석유의 라벨링을 해주며 진행했다.