본문 바로가기

너비 우선 탐색(BFS)9

[Programmers] 타겟 넘버 https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 주어지는 숫자들을 하나씩 순차적으로 더하거나 뺀 결과값을 구하는 재귀 함수를 만들어 문제를 해결한다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include using namespace std; void Add(const vector& v, const int& t, int& cnt, int i, int sum) { if (i == v.s.. 2024. 1. 7.
[Baekjoon] 11967번: 불켜기 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 그래프 탐색 알고리즘과 관련한 문제는 자신 있다고 생각했는데, 문제에서 요구하는 것 잘못 파악 + 문제에 들어있는 함정 때문에 처음 작성했던 코드가 왜 틀렸는지 이해하느라 엄청난 시간을 소모해버렸당 문제 해결 과정 착안 시작 지점으로부터 방을 방문할 때마다, 방에 존재하는 모든 스위치를 켜면서 불이 켜진 방의 갯수를 증가시킨다. 이후 인접한 방.. 2023. 12. 14.
[Baekjoon] 1012번: 유기농 배추 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 해결 과정 착안 상하좌우로 연결된 배추들 사이에는 하나의 배추흰지렁이만 있어도 해충 예방이 가능하므로, 이를 표현하기 위해 편의상 아래와 같은 과정을 주어지는 배추밭 모양에 따라 반복적으로 수행하여 필요한 총 배추흰지렁이의 수를 계산한다. 배추가 심어진 땅이 발견되면 필요한 배추흰지렁이의 수를 1만큼 증가시킨다. 깊이 우선 탐색(depth-first search, DFS) 또는 너비 우선 탐색(bread.. 2023. 8. 24.
[Baekjoon] 14502번: 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해결 과정 착안 주어지는 연구소 모양에 대하여 백트래킹(backtracking, 퇴각검색) 알고리즘을 통해 빈 공간에 벽 3개를 세우면서, 바이러스 확산 예상 결과를 너비 우선 탐색(breadth-first search, BFS)을 통해 구하고자 하였다. 구현 편의상 벽의 개수를 파악하기 쉽도록 세우고자 하는 벽의 번호를 3, 4, 5로 정하여 프로그래밍 하였다. 한편 백트래킹 알고리즘에 기반하여 너비 .. 2023. 8. 15.
[Baekjoon] 16234번: 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 과정 착안 너비 우선 탐색(breadth-first search, BFS) 알고리즘을 응용하여 날짜 별로 연합이 존재할 수 있는지 탐색해보고, 연합이 존재한다면 각 연합 별로 연합에 속하는 나라들의 인구를 산술평균 값으로 갱신하는 과정을 통해 문제를 해결하고자 하였다. 연합이 존재할 수 있는지 판단하는 과정에서, 인접한 나라와 직접적으로 국경선이 개방되어 연결되지 않더라도.. 2023. 7. 26.
[Baekjoon] 18405번: 경쟁적 전염 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제 해결 과정 착안 우선순위 큐(priority queue) 자료 구조를 활용하여, 바이러스 번호가 낮은 순으로 먼저 너비 우선 탐색(breadth-first search, BFS)을 수행함으로써 문제를 해결하고자 하였다. * 우선순위 큐 대신, 배열 및 정렬 알고리즘을 사용하여 해결하면 속도 측면에서 더 유리한 것 같다. 구현 좌표를 나타내기 위한 구조체 Coor.. 2023. 7. 21.

티스토리툴바