반응형 BFS3 게임맵 최단거리 [programmers&leetcode] 문제 풀이 처음 이 문제를 프로그래머스에서 마주쳤을때는 풀지 못했다. 나중에 풀고 넘어가야할 문제로 넘겼는데 오늘 leetcode 에서 비슷한 문제를 만나게 되고, 해당 문제의 hint를 보게 되어 ‘이렇게 푸는 거 구나!’ 싶어서 풀게 되었다. 그럼 저 문제를 풀기 전에 hint를 주었던 leetcode 오늘의 문제부터 살펴보기로 하자. hint 부분에 Do a breadth first search to find the shortest path. 라고 적혀 있는걸 보고 bfs로 푸는구나 하고 알게 되었다. leetcode의 문제를 보면 각 점 좌표에서 여덟방향으로 0이 있는지 조사후 해당 경로를 다음 단계에서 움직일 예정이라고 리스트에 저장한다. 예를 들어, 3*3 행렬(0-index)의 [1,1] 의.. 2022. 5. 16. tree 문제 2개 (dfs & bfs) [leetcode] DFS 가장 깊은 노드 끼리 합산 뒤, 반환하는 문제다. 이 문제의 경우 dfs( Depth First Search )를 통해 풀면 된다. 재귀 함수를 사용하고, 함수의 반환 값은 [ 노드의 값, 노드의 깊이 ] 를 반환 한다. left 와 right 값을 반환 받았을때 노드의 깊이 를 비교한 뒤, left 노드의 깊이 > right 노드의 깊이 일 경우 left 노드 정보 ( [ 노드의 값, 노드의 깊이] ) 를 반환 left 노드의 깊이 == right 노드의 깊이 일 경우 노드 값 합산 ( left+right노드의 값, left(right) 노드의 깊이] ) 를 반환 left 노드의 깊이 < right 노드의 깊이 일 경우 right 노드 정보 ( [ 노드의 값, 노드의 깊이] ) 를 반환 해당 조.. 2022. 5. 16. 전력망을 둘로 나누기 [프로그래머스] 문제 넋두리 나는 문제를 set으로 풀려고 했다. 계획은 이랬다. 특정 node(ex.wires[0][0]) 를 left set에 넣는다. wires중 하나를 제거한다. 잘라진(하나가 제거된) wires 배열을 루프돌면서 left set에 wire[0], wire[1]이 존재한다면 left에 추가 한다. 루프가 끝난시점에 left에 담긴 node 와 그렇지 않은 node set 간의 갯수 차이를 리턴 2-4번 (n-1)번 반복 하면서 차이가 제일 작은 값을 answer로 저장 그런데 자꾸 틀렸다. 틀린 이유를 못찾았는데 예상하기로는 left set에 담기는 조건이 wire[0] 이나, wire[1]이 left set에 존재하는지 여부 였는데, (⇒ if wire[0] in left or wire[1] i.. 2021. 10. 9. 이전 1 다음 반응형
