본문 바로가기

BFS

백준 S2 1260 : DFS와 BFS 🅾️ [문제] 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [풀이] 소요시간 : 46분 import java.io.*; import java.util.*; public class Main { /* 입출력 */ sta.. 더보기
백준 S3 2606 : 바이러스 🅾️ [문제] 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의.. 더보기
프로그래머스 Lv.3 : 네트워크 🅾️ [문제] 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. program.. 더보기
백준 S1 2178 : 미로 탐색 🅾️ [문제] N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [풀이] import.. 더보기
프로그래머스 Lv.2 : 게임 맵 최단거리 🅾️ [문제] ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다. 첫 번째 방법은 11개.. 더보기
알고리즘 : BFS (2) 실습! 코딩테스트 풀이 도전 내가 풀어볼 BFS 코테는 프로그래머스의 '게임 맵 최단거리'이다. 우선 문제를 읽어보면 캐릭터는 이차원 배열의 0,0에 위치하고, 진영은 n-1, m-1에 위치한다. (이차원 배열의 크기를 [n][m]으로 가정 시) 즉, 왼쪽 위와 오른쪽 아래에 각각 위치하기 때문에 캐릭터는 최단으로 이동하려면 오른쪽과 아래로만 이동하는 것이 좋다. 물론 길이 왼쪽이나 위밖에 없다면 그 경우도 고려하게 되겠지만. 어쨌든 풀이를 시작해보자! 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 먼저 나는 크기가 똑같은 boolean 타입 이차원 배열 하나를 생성해주기로 결심했다.. 더보기
알고리즘 : BFS (1) 넓이 탐색 알고리즘이란 무엇인가 알고리즘 하면 왠지 'BFS', 'DFS'가 가장 인지도가 높은 것 같다(?) 대충 알 것 같은 DFS를 뒤로 하고, BFS의 이론을 공부해보려 한다. 우선 둘다 그래프 탐색 알고리즘이다. 자료구조 중 가장 어렵다고 생각하는 '그래프' ..는 다음에 차차 제대로 공부하기로 하고. 원래 스키도 고급부터 타면서 배운다고, 나는 알고리즘 먼저 배우고 그래프를 공부해보려고 한다. DFS와 BFS 모두 시간 복잡도는 O(N)이다. DFS는 깊이 탐색 알고리즘, BFS는 넓이 탐색 알고리즘! 가장 간단하게 풀이하자면, DFS → 재귀, stack BFS → queue (deque) 일반적으로 DFS 보다 BFS가 조금 더 빠르다고 한다. 이런 둘의 사용 여부 구분은 크게 이러하다. DFS → 특정 목표 node를 .. 더보기

티스토리툴바