병아리 개발자의 실력 양성기

트리를 레벨별로 출력하라는 문제. 예를 들어, Root 가 1이고, 좌우 Child가 2, 3, 그 다음 세대가 각각 4/5, 6/7인 경우에는 -> [[1],[2,3],[4,5,6,7]] 처럼 출력하는 문제이다.이건 레이어가 중요한 문제BFS의 경우에 어떤 경우는 queue에 자식노드를 계속 추가하면서 while로 해서 다 방문하고, 지금 경우는 for 로 딱 현재 queue 길이만큼만 방문하되 자식 노드는 추가는 계속 해 나가기도 한다. 후자의 경우는 레벨별로 방문해야 하거나, 아니면 최단거리 문제를 풀어야 할 때 꼭 지켜줘야 하는 것이다. 아래 코드에 설명을 달아 둔다.from collections import dequeclass Solution: def levelOrder(self, root..

벽으로 둘러싸인 공간, 즉 방의 갯수를 구하는 Counting Rooms 라는 문제가 있다. https://cses.fi/problemset/task/1192/ CSES - Counting Rooms cses.fi 이는 DFS의 응용 형태로 푸는 것이다. DFS는 한 점에서 출발해 닿을 수 있는 미 방문점을 모두 방문하는 것이다. 방문할 때 마다 방문된 점을 표시하되 끝까지 방문이 되면 돌아온다. 이와 유사한 과정인 backtracking은 방문시마다 어떤 조건에 대해 확인하는 절차를 거쳐, 그 조건이 만족되지 않으면 방문을 종료하는 것이다. DFS에서 기본적으로 검증하는 조건은 바로 '방문여부'가 된다. 이미 방문된 것은 다시 방문하지 않는다. 이를 위해 방문된 노드에 대한 기호를 모아놓는 일을 set..