BFS1 [프로그래머스] 거리두기 확인하기 (C++) 유형 : DFS/BFS 코멘트 카카오 문제이지만 되게 삼성 같은(?) 문제다. 맨 처음에는 그냥 시뮬레이션처럼 풀었는데, 몇 개의 테스트 케이스가 통과하지 못해서 DFS/BFS로 접근했다. 문제에서 '맨해튼 거리'라고 어렵게 말했지만, 전형적인 BFS로 한 칸씩 이동할 때마다 거리를 +1 해주면 되는 문제이다. 설명 핵심 Idea : 모든 사람이 있는 좌표에서 BFS로 나와의 거리가 2 이하인 좌표가 하나라도 있는지 검사한다. 5개의 대기실마다 각각 아래 과정을 반복한다. 5*5의 모든 좌표마다, 이번 자리에 사람('P')이 앉아있는 경우에만 탐색을 진행한다. ('P'가 아니면 continue) BFS를 돌면서, 나와 다른 모든 사람의 거리를 구한다. (bfs()함수, 파티션('X')은 방문할 수 없음을.. 2021. 7. 17. 이전 1 다음