[취업준비일지] - 139

오늘은 알고리즘 풀이 및 기존에 풀었던 알고리즘 정리와

정처기 강의, 이력서 지원 위주로 진행했다..

 

(1).백준 11403번 경로 찾기는 조금 생소한 문제였다.

일반적으로 제공되는 그래프나 경로 문제는 길이 존재할 경우 양방향인데
편도라는 말을 따로 하지 않지만 예제를 보면 단방향의 간선임을 알 수 있다.

처음에는 양방향의 처리만 진행했기 때문에 많이 어색해서 
평소 하던대로 처리를 해도 되는지 잘 몰랐지만
곰곰히 생각해보면 어차피 존재하는 경로만 조회하는 방식으로 하기 때문에
단방향, 양방향 여부는 중요하지 않았다.

이전에 풀었던 케빈 베이컨의 법칙 처럼
3중 for문을 사용해 현재 경로와 목적 경로를 지정한 뒤
그 사이에 들어갈 정점을 지정해 a -> b로 갈 경우
a -> c -> b로 갈 수 있으면 경로가 있음(1)을 표기하는 것이다.

좌표는 당연히 이중 배열 형태로 사용하기 때문에
j에서 k로 가는 경로의 존재 여부를 구할 때는 경유지인 i를 끼워넣어 아래처럼 방문한다. 
[j][i] -> [i][k]

const input = `7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0`.split('\n')

const map = []

for(let i = 1 ; i < input.length ; i++){
    map.push(input[i].split(' ').map(Number))
}

for(let i = 0 ; i < map.length ; i++){
    for(let j = 0 ; j < map.length ; j++){
        for(let k = 0 ; k < map.length ; k++){
            if(map[j][i] && map[i][k]){
                map[j][k] = 1
            }
        }
    }
}

console.log(map.map(el => el.join(' ')).join('\n'))