[python]백준 알고리즘 11403 경로찾기

안녕하세요! 코딩하는 JAY입니다.  다들 2018년 새해계획은 잘 세우셨나요?!ㅎㅎㅎ

거창한게 아니더라도 새해에 각오, 목표 하나씩 세우면 동기부여도 되고 좋은 것 같습니다.

     (좋아연~:D)

오늘 부터 '백준 알고리즘' 문제 포스팅을 하려고 합니다! 알고리즘에 대해서 많이 부족하기도 하고, 소프트웨어 개발할때 많은 도움이 될 것 같아서 올해부터 꾸준히 하려고 합니다.

※ 11403번 경로찾기

오늘 풀어볼 문제는 '경로찾기'입니다. DFS(깊이우선탐색) 문제인데요. 예제입력1을 기준으로 문제를 설명하면 이렇습니다.

(i, j)가 1일 경우 i에서 j로 가는 경로가 있다는 의미 입니다. 오른쪽 그림을 보면 이해하기 쉬우시죠?! 자, 여기서 i에서 j로 가는 경로가 있으면 j에서 i로 가는 경로도 있다는 의미입니다. 그럼 (2, 0)이 1이면 출력으로 (0, 2)도 1이 되야겠죠?

여기까지는 쉽게 다 이해하셨을거라 생각합니다. 저도 여기까지는 이해했는데, 문제점이 (0, 0), (1, 1), (2, 2) 지점이 왜 1이 되는지 이해가 안갔습니다.  이 부분을 이해하려면 플로이드-워셜 알고리즘을 아셔야 합니다. 사실 이 문제를 푸는데 있어서 몰라도 풀 수는 있는데 개인적으로 알고나니까 더 이해하기 쉽더라고요. 

간단히 설명하면 플로이드-워셜 알고리즘은 모든 정점에 대한 경로를 계산하는 알고리즘입니다.

위키백과 : https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

다시 문제로 돌아와서 설명하자면 (0, 0), (1, 1), (2, 2)를 갈 수 있는 경로는 (0, 0)의 경우 0->1->0 혹은 0->2->0 이 될 수 있습니다. 나머지로 마찬가지입니다. 그림으로 정리하면 아래와 같습니다.

위 내용을 베이스로 실제 코딩을 짜보겠습니다. 코딩은 python으로 하였습니다.

N = int(input())
 
inputMap = [[0 for col in range(0, N)] for row in range(0, N)]
 
for i in range(0, N) :
    for j, m in enumerate(map(int, input().split())) :
        inputMap[i][j] = m
 
#플로이드 워셜 알고리즘(Floyd Warshall Algorithm) 이용
for k in range(0, N) :
    for i in range(0, N) :
        for j in range(0, N):
            if inputMap[i][k] and inputMap[k][j] :
                inputMap[i][j] = 1
 
for i in range(0, N) :
    _str = ""
    for j in range(0, N) :
        _str += str(inputMap[i][j]) +  " "
    print(_str)
 

코드를 보면 모든 정점들을 확인하기 위해 변수 k가 들어가 있는 for문이 있습니다. i에서 j로 가는 경로를 k를 통해 모든 경로를 체크하게 됩니다. 출력을 확인해 보면 아주 잘 동작합니다!

아! 참고로 배열값을 입력받는 부분에서 map()함수와 split()함수가 사용되었는데요.  split()함수는 "0 1 0"이렇게 입력되는 문자열을 ' '(스페이스)를 기준으로 나눠주는 함수이고, 나눠진 값들을 int()함수를 사용해 int값으로 바꿔줍니다. 이때, map(f, iterable)은 함수(f)와 반복 가능한(iterable) 자료형을 입력으로 받아서 입력받은 자료형의 각 요소가 함수 f에 의해 수행된 결과를 묶어서 리턴해줍니다.

(map을 사용할 경우)

(map을 사용하지 않을 경우)

파이썬에 map()을 처음 접했을때 정말 신세계였습니다.ㅋㅋㅋㅋ 반복적인 작업이 필요할때 유용하게 쓰이더군요. 이상으로 오늘의 포스팅을 마치겠습니다. 모두들 즐거운 코딩, 재밌는 코드 생산하세요~:D