목록BFS (24)

반갑습니다!

[백준] 2638 치즈

2638번: 치즈 www.acmicpc.net 풀이 치즈 외부 공기와 접촉한 치즈들을 체크하는 것이 관건인 문제이다. 문제에 모는종이의 맨 가장자리에는 치즈가 놓이지 않는다 명시되어 있으므로 (0, 0)은 비어있는 칸임을 알 수 있다. 그래서 (0,0)에서 BFS로 탐색하여 외부 공기와 접촉한 치즈를 체크하여 해결하였다. BFS 탐색을 마쳤을 때 2차원 배열 visited의 값이 2 이상인 경우에는 외부 공기와 접축한 치즈라는 의미이므로 제거하였다. 코드 C++ #include #include #include #include using namespace std; int n, m, cnt; int map[101][101], visited[101][101]; const int dx[] = { -1, 0, 1..
알고리즘 문제 풀이 2020. 4. 11. 21:56
[프로그래머스] 지형 이동

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 해당 문제는 크게 3단계로 풀이된다. 사다리 설치가 필요없는 지형들 그룹화 그룹화된 지형들 사이를 이동하는 최소 비용 저장 저장된 최소 비용들로 MST 생성 1. 사다리 설치가 필요없는 지형들 그룹화 DFS 혹은 BFS를 사용하여 사다리가 필요없이 이동가능한 지형들을 하나의 그룹으로 표시한다. 아래의 코드에서는 방문 여부를 체크하는 visited배열을 int형으로 선언하여 방문 여부의 체크와 그룹 표시를 같이 진행하였다. 2. 그룹화된 지형들 사이를 이동하는 최소 비용 저장 visited배열에 그룹을 구..
알고리즘 문제 풀이 2020. 4. 4. 22:39
[프로그래머스] 카카오 프렌즈 컬러링 북

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전형적인 BFS문제이다. [0, 0] 부터 [N, M] 까지 반복문을 돌면서 picture의 값이 0이 아닐 때 마다 BFS를 실행하여 BFS가 실행된 횟수가 구역의 수가 되고, BFS의 리턴값을 통해 구역의 최대 넓이 또한 구할 수 있다. 코드 #include #include using namespace std; int M, N; vector visited; const int dx[] = {-1 ,0, 1, 0}, dy[] = {0, -1, 0, 1}; bool inRange(int x, int y){..
알고리즘 문제 풀이 2020. 4. 3. 17:43
[프로그래머스] 가장 먼 노드

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 BFS를 통해 1번 노드부터 모든점들을 방문하고 가장 오래 걸린 노드들의 개수를 출력해주면 된다. 초기 입력 값으로 들어오는 edge 배열을 인접 리스트로 변환하여 풀이하였다. 코드 #include #include #include #include #include using namespace std; vector adj; vector visited; int bfs(){ queue q; q.push(1); visited[1] = 0; int ret = 0; while(!q.empty()){ int cur =..
알고리즘 문제 풀이 2020. 4. 2. 17:33
이전 Prev 1 2 3 4 5 Next 다음