1620번, 11403번 풀이

8681 단어 algorithmalgorithm

solved.ac에서 추천해준거 암거나 풀었다.

1. 나는야 포켓몬 마스터 이다솜

링크 - https://www.acmicpc.net/problem/1620

코드

import sys

input = sys.stdin.readline

n,m = map(int,input().split())

#딕셔너리
pokemon={}
reverse={}
#포켓몬 입력
for i in range(1,n+1):
    name = input().rstrip()
    pokemon[name]=str(i)
    reverse[str(i)]=name

#문제 입력
for i in range(m):
    q = input().rstrip()
    if pokemon.get(q):
        print(pokemon.get(q))
    else:
        print(reverse.get(q))

딕셔너리를 이용해서 이름과 번호를 찾아주었다.
{번호:이름}, {이름:번호} 2개의 딕셔너리를 만들어줌

문제 읽다가 사이트 잘못 들어온 줄 알고 당황했다. 다솜씨 필력 좋으시네;

2. 경로 찾기

링크 - https://www.acmicpc.net/problem/11403

코드

import sys

input = sys.stdin.readline
INF = int(1e9)

#정점의 개수
n = int(input())

#인접행렬 받아오기
graph = [list(map(int,input().split())) for i in range(n)]

#플로이드 워셜
for k in range(n):
    for i in range(n):
        for j in range(n):
            if graph[i][k]==1 and graph[k][j]==1:
                graph[i][j]=1

for i in range(n):
    for j in range(n):
        print(graph[i][j],end=" ")
    print()

모든 노드에서 모든 노드의 경로를 탐색해야 하므로 플로이드 워셜 알고리즘을 사용했다.

이미 (i,j)번째에 간선이 있는건 체크해줄 필요가 없으므로 거쳐갈 수 있는 경우만 체크를 해주었다.

좋은 웹페이지 즐겨찾기