프로그래밍/문제 풀기

백준27882 가희와 지하철역 저장 시스템 2 [python]

jtw7977 2024. 8. 30. 08:09

문제 링크: https://www.acmicpc.net/problem/27882

 

문제

요청 노드 r번 노드에서 지하철역 s에 대한 정보를 출력해 달라는 요청이 수행되는 시간은 아래와 같이 구할 수 있습니다.

  • r번 노드에서 전송 시간이 가장 적은 cache 노드를 찾습니다. 만약에 그러한 것이 여러 개라면, id가 가장 작은 cache 노드를 찾습니다. 이 노드를 c1번 노드라 할 때
    • c1번 노드에 지하철역 s에 대한 정보가 있는 경우 2×(r번 노드에서 c1번 노드로 데이터를 보내는 전송 시간)
    • 그렇지 않은 경우 2×(r번 노드에서 c1번 노드로 데이터를 보내는 전송 시간 + c1번 노드에서 bucket 노드로 데이터를 보내는 전송 시간)

지하철역에 대한 정보를 출력해 달라는 요청이 Q번 주어졌을 때, 각각의 요청이 수행되는 시간을 구해주세요.

 

제한

  • 1 ≤ n ≤ 2×105
  • 1 ≤ m ≤ 300
  • 1 ≤ h ≤ n
  • 1 ≤ Q ≤ 2×105
  • 1 ≤ k ≤ mC2
  • 1 ≤ rt ≤ 300
  • 역 이름은 길이가 1 이상 10 이하이며, 대소문자와 숫자로만 이루어져 있습니다.
  • 멍멍철도공사에서 관리하는 n개의 역 이름이 중복되는 경우는 없습니다.
  • 역에 대한 정보를 출력하라는 요청은 cache 노드나 bucket 노드에서 이루어지지 않습니다.
  • bucket 노드는 하나만 있으며, cache 노드는 최소 하나 이상 있습니다.
  • 서로 다른 노드 번호를 가진 임의의 두 노드를 직접 연결하는 회선은 0개 또는 1개입니다.
  • bucket 노드로부터 bucket 노드가 아닌 다른 임의의 노드로 1개 이상의 회선을 거치면 갈 수 있습니다.

 

문제 풀이

문제 풀이 아이디어

1. 노드 정보를 입력받고 캐시노드->요청노드의 최단거리와 버켓노드->캐시노드의 최단거리를 미리구한다. 노드수가 최대 300이므로 플로이드-워셜로 가능하다.

2. 쿼리를 처리한다.

3. 요청노드의 가장 가까운 캐시노드에 요청역이 있으면 요청 시간을 갱신하고 시간을 출력한다.

만약 요청 노드에 요청역이 없으면 캐시노드에 요청역을 저장한다.

4. 요청역을 저장할때 용량이 초과되면 요청이 가장 없었던(최근 요청이 가장 먼 시간의) 노드를 저장 메모리에서 지운다.

5. 쿼리마다 반복한다.

 

구현

기본 초기화

def main():
    #init
    N,M,H,Q=map(int,input().split())
    stations=set()
    for _ in range(N):
        stations.add(input().strip())
    node_info={} #노드 정보를 담을 dict
    bucket=[]
    cache=[]
    request=[]
    gr=[[INF]*(M)for _ in range(M)] #그래프 초기화
    for i in range(M):gr[i][i]=0

 

노드 정보 입력

def main():
    #node informations input
    for i in range(M):
        node_name,node_type=input().strip().split()
        if node_type=='B': #버켓 노드
            bucket.append(node_name)
        elif node_type=='C': #캐시 노드
            cache.append(node_name)
        else:
            request.append(node_name) #요청 노드
        node_info[node_name]=i #그래프에 저장할 인덱스를 저장
        node_info[i]=node_name

 

그래프 입력

def floyd(gr,M): #플로이드 워셜
	for i in range(M):
		for j in range(M):
			for k in range(M):
				gr[j][k]=min(gr[j][k],gr[j][i]+gr[i][k])
	return gr


def main():
    #graph input
    for _ in range(int(input())):
        node1,node2,rt = input().strip().split()
        node1_index,node2_index=node_info[node1],node_info[node2]
        gr[node1_index][node2_index]=int(rt)
        gr[node2_index][node1_index]=int(rt)
    gr=floyd(gr,M)
    cache_node_db={o:{'db':OrderedDict({}),'capacity':0} for o in cache} #캐시 노드 정보들을 담을 dict, db키는 저장되어 있는역 dict, capacity는 캐시노드 용량

여기서 캐시노드에 저장된 역을 저장하기 위해 OrderedDict을 사용하였다. 왜 사용했는지는 나중에 설명하겠습니다.

 

요청노드 전처리

def main():
    request_node_db={}
    #each request node minimum distance to cache node
    for n in request:
        j=node_info[n]
        k=INF
        b=1e9+1
        for p in cache:
            i=node_info[p]
            rk=gr[j][i]
            if (rk<k)or (rk==k and int(p)<int(b)): #최단 경로 이거나, 거리가 같더라도 캐시노드의 번호가 작다면 요청노드->캐시노드의 경로 업데이트
                b=node_info[i]
                k=rk
        request_node_db[n]={'short_node_name':b,'short_distance':k} #최단거리 노드명, 거리를 저장

 

쿼리 처리

def main():
    #processing quarry
    for _ in range(Q):
        p_node_name,station_name=input().strip().split()
        print(process(p_node_name,station_name,request_node_db,cache_node_db,node_info,node_info[bucket[0]],gr,H))

 

캐시 노드의 처리 및 요청시간 처리

def process(R_node_name,station_name,request_node_db,cache_node_db,node_info,bucket_node,gr,h):
    p = request_node_db[R_node_name]['short_node_name'] #최단거리 캐시 노드명
    g = cache_node_db[p]['db'] #캐시노드의 저장된 역들
    ans=request_node_db[R_node_name]['short_distance']*2 #기본적으로 캐시노드와 통신하면 생기는 시간
    if station_name in g: #요청역이 이미 캐시에 저장되어 있으면 바로 리턴
        del g[station_name] #업데이트를 하기위해 제거
        g[station_name]=0 #dict가장 뒤에 추가
        return ans
    else: #요청역이 캐시노드에 없다면
        if station_name in g:
            del[station_name]
        elif cache_node_db[p]['capacity']==h: #캐시노드 db 용량이 최대라면
            cache_node_db[p]['capacity']-=1 #용량-1
            g.popitem(last=False) #가장 앞에 키 제거
        g[station_name]=0 #캐시 노드에 요청역을 저장
        cache_node_db[p]['capacity']+=1 #용량 +1
        r=gr[node_info[p]][bucket_node] #캐시노드와 버켓노드의 거리만큼 시간추가됨
        return ans+r*2

여기서 OrderedDict을 사용했는지 나오게 된다. OrderedDict는 순서를 유지하는 dict인데 이게 왜 중요하나면, 캐시노드에는 앞으로 갈수록 요청이 없던 노드 뒤로 갈수록 최신요청노드이다.

하지만 이걸 리스트로 구현하기에는 캐시노드에 요청역이 이미 저장되어 있으면 중간에서 제거하고 뒤에 추가해야하는데 요청역이 db에서 찾는걸 O(n) 제거하는걸 O(n)으로 하기에는 시간조건이 빡빡함+최대 용량이 2*10^5이기 때문에 OrderedDict을 선택했다. dict에서는 제거가 O(1)이므로 db중간에 있는역이 요청들어와도 제거 및 추가를 상수시간으로 해결가능하다. 그리고 dict에서 가장 앞의 요소를 제거 할때도 O(1)의 시간으로 제거 가능한것이 OrderedDict이므로 OrderedDict.popitem()을 하면된다 last=True이면 가장 뒤에것이 제거가 가능하다.

 

전체코드

더보기 
from collections import OrderedDict
input=open(0).readline
INF=float('inf')

def floyd(gr,M):
	for i in range(M):
		for j in range(M):
			for k in range(M):
				gr[j][k]=min(gr[j][k],gr[j][i]+gr[i][k])
	return gr
	
#important function
def process(R_node_name,station_name,request_node_db,cache_node_db,node_info,bucket_node,gr,h):
    p = request_node_db[R_node_name]['short_node_name']
    g = cache_node_db[p]['db']
    ans=request_node_db[R_node_name]['short_distance']*2
    if station_name in g:
        del g[station_name]
        g[station_name]=0
        return ans
    else:
        if station_name in g:
            del[station_name]
        elif cache_node_db[p]['capacity']==h:
            cache_node_db[p]['capacity']-=1
            g.popitem(last=False)
        g[station_name]=0
        cache_node_db[p]['capacity']+=1
        r=gr[node_info[p]][bucket_node]
        return ans+r*2
	
def main():
    #init
    N,M,H,Q=map(int,input().split())
    stations=set()
    for _ in range(N):
        stations.add(input().strip())
    node_info={}
    bucket=[]
    cache=[]
    request=[]
    gr=[[INF]*(M)for _ in range(M)]
    for i in range(M):gr[i][i]=0
    
    #node informations input
    for i in range(M):
        node_name,node_type=input().strip().split()
        if node_type=='B':
            bucket.append(node_name)
        elif node_type=='C':
            cache.append(node_name)
        else:
            request.append(node_name)
        node_info[node_name]=i
        node_info[i]=node_name
    
    #graph input
    for _ in range(int(input())):
        node1,node2,rt = input().strip().split()
        node1_index,node2_index=node_info[node1],node_info[node2]
        gr[node1_index][node2_index]=int(rt)
        gr[node2_index][node1_index]=int(rt)
    gr=floyd(gr,M)
    request_node_db={}
    cache_node_db={o:{'db':OrderedDict({}),'capacity':0} for o in cache}
    
    #each request node minimum distance to cache node
    for n in request:
        j=node_info[n]
        k=INF
        b=1e9+1
        for p in cache:
            i=node_info[p]
            rk=gr[j][i]
            if (rk<k)or (rk==k and int(p)<int(b)):
                b=node_info[i]
                k=rk
        request_node_db[n]={'short_node_name':b,'short_distance':k} 
    
    #processing quarry
    for _ in range(Q):
        p_node_name,station_name=input().strip().split()
        print(process(p_node_name,station_name,request_node_db,cache_node_db,node_info,node_info[bucket[0]],gr,H))
main()

 

 

회고

이문제는 제가 처음으로 푸는 플4문제 였지만 재밌는 문제였습니다. 구현+그래프라서 제가 좋아하는 분야?였습니다. 생각을 좀 하느라 푸는데2시간30분 정도 걸렸던것 같은데 풀만했습니다. 가희와 함께하는 코테 문제들에는 괜찮은 문제가 많은것 같았습니다.

 

문제 태그

#구현 #그래프 이론 #최단거리 #플로이드-워셜 #자료구조 #해시맵

'프로그래밍 > 문제 풀기' 카테고리의 다른 글

백준 9702 LIS [python]  (0) 2024.09.24
백준30035 Tier and Rank [python]  (0) 2024.09.10
백준27888 가희와 지하철역 저장 시스템 1 [python]  (1) 2024.08.31
백준4278 Go [python]  (0) 2024.08.29
백준31476 :blob_twintail_thinking: [python]  (0) 2024.08.26

'프로그래밍/문제 풀기'의 다른글

  • 현재글백준27882 가희와 지하철역 저장 시스템 2 [python]

관련글

티스토리툴바