알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 순위

* 문제유형이 그래프인데 다른방법으로 풀어서 다시 풀어봐야 할 문제 문제 : https://programmers.co.kr/learn/courses/30/lessons/49191 풀이 i번 선수를 이긴 선수의 명단인 win과 i번 선수에게 진 선수의 명단인 lose를 만든다. 그리고 results를 확인해서 A가 B에게 이기면 B번 선수의 이긴명단에 A를, A번 선수에게 진 명단에 B를 추가한다. setwin[101]; setlose[101]; for(auto i : results){ win[i[1]].insert(i[0]); lose[i[0]].insert(i[1]); } input : [4, 3] 4는 3에게 이겼으므로 win[3]에 4를 추가한다. 3은 4에게 졌으므로 lose[4]은 3를 추가한다..

2019. 12. 4. 23:00
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 가장 먼 노드

문제 : https://programmers.co.kr/learn/courses/30/lessons/49189 서론 그래프 문제. 풀이 그래프를 탐색해서 가장 먼 노드들을 찾는다. 그래프 탐색 알고리즘은 DFS/BFS가 있는데, 최단거리 문제를 제외하고는 항상 DFS로 구현했던지라 이번에도 그렇게 했다. 그리고 문제 발생 3번 노드는 1번노드에서 한칸 떨어져 있지만 1 - 2 - 3순으로 탐색해서 2칸 떨어진것으로 인식할 수 있다. 방문할때 조건을 잘 설정해주면 될것 같기도 하지만 애초에 이런 문제가 없는 BFS로 다시 구현했다. 그래프를 만들고 노드들의 거리를 저장하는 배열을 만든다. BFS로 탐색하면서 방문할 노드의 거리는 이전 노드의 거리에서 +1한다. 그리고 노드의 거리 중 최대값은 변수에 저장하..

2019. 10. 28. 10:04