Python으로 푸는 SW Expert Academy 1219. 길찾기

SW Expert Academy 1219. 길찾기

도시들의 간의 간선 정보가 나와 있고,

가는 길의 개수와 상관없이 한가지 길이라도 

도시 0 에서 도시 99로 갈 수 있는 길이 존재하는지 

확인하는 코드를 구현해야 한다.

삼성 SW Expert Academy에서 푼 문제 리스트 보기

github에서 코드 보기

문제 조건

출발점은 0, 도착점은 99로 표현된다.

도시 사이의 간선은 일방통행으로 연결되어 있으므로 되돌아오는 것이 불가능하다.

그 말은 즉, 도시에 들어갈 순 있어도 나갈 순 없는 도시도 존재할 수도 있다는 말이다. (사이트에 예시로 나와 있는 10번 도시가 그렇다)

문제 풀이

문제에서는 size 100의 정적배열 2개를 선언하여 각 정점 번호를 주소로 사용하고, 저장되는 데이터는 각 정점에서 도착하는 정점의 번호를 저장하는 것을 제안하였다.

그러나 이 경우에는 도시가 적을 경우에는 불필요한 메모리를 사용할 수 있다는 단점이 있다.

그러므로 배열이 아닌 dictionary를 사용하여 도시 간의 간선의 정보를 저장해두었다. 

첫번째 테스트 케이스를 dictionary를 사용해 도시 간의 정보를 저장한다면 데이터는 다음과 같이 저장된다. 

{'0': ['1', 2], '1': ['4', 3], '4': ['8', 3], '2': ['9', 5], '5': ['6', 7], '7': ['99', 9], '9': ['8', 10], '6': ['10'], '3': ['7']}

연결된 도시들이 무엇인지 알고 싶다면 도시 번호를 키 값으로 Dictionary를 뒤지면 된다.

예를 들어, '0'번 도시에 연결된 도시는 리스트에 ['1','2'] 와 같이 저장되어 있다.

방문한 도시의 인접 도시들의 정보를 탐색하여 도착지점 (도시 '99')이 있는지 확인한다. 

없을 경우에는 그 인접도시들을 탐색하기 위해 다음 탐색 도시 리스트에 넣어준다.

도착 지점이 나오지 않으면 모든 도시를 다 탐색할때까지 이 작업을 반복한다.

파이썬 코드

def gen():
    table = dict()
    t, e = map(int, input().strip().split())
 
    start = None
    for v in map(int, input().strip().split()):
        if start is None:
            start = v
        else:
            if str(start) in table:
                table[str(start)].append(str(v))
            else:
                table[str(start)] = [str(v)]
            start = None
    yield t, table
 
 
def solve(table):
    visited = [False] * 100
    next_pos = table['0']
    while next_pos:
        pos = next_pos.pop()
 
        # 방문한 도시는 패쓰
        if visited[int(pos)]:
            continue
        else:
            # 방문하지 않은 도시라면 연결된 도시들 확인
            add_next_pos = []
            if pos in table:
                add_next_pos = table[pos]
            # 다음 도시에 도착 지점이 있는지 확인
            if '99' in add_next_pos:
                return 1
            
            next_pos.extend(add_next_pos)
    return 0
 
 
if __name__ == "__main__":
    for i in range(10):
        for t, table in gen():
            print("#{0} {1}".format(t, solve(table)))
 

#1219 길찾기 #sw expert 1219 #sw expert 1219. 길찾기 python #sw expert 1219 길찾기 #파이썬 sw expert 1219 # SW Expert Academy