전체태그 보기

#BFS (13개의 포스트)

백준 2617 구슬 찾기
skyepodium

백준 2617 구슬 찾기

2019년 9월 14일0개의 댓글
문제 중간 번호가 될 수 없는 구슬의 개수를 구하는 문제 1. n 구슬의 개수 (1 ≤ n ≤ 99, n은 홀수) 2. m 무게 정보의 개수 (1 ≤ M ≤ N(N-1)/2) 3. 설명 만약 문제의 입력이 다음과 같이 주어지면
BFS는 낯설어서
skyepodium

BFS는 낯설어서

2019년 7월 28일2개의 댓글
BFS (Breath-First-Search, 너비 우선 탐색) 은 시작점에 인접한 다른 정점을 모두 방문하고, 다른 정점에 대해서도 인접한 또 다른 정점을 모두 방문하는 방법입니다. 여기서, 인접하다는 의미는 두 정점이 하나의 간선으로 연결되어 있다는 의미입니다. 라고.. 저는 누가 물어보면 말할래요 ~찡긋 그림을 통해 설명드리겠습니다. ...
코드포스 520B Two Buttons
skyepodium

코드포스 520B Two Buttons

2019년 7월 27일0개의 댓글
빨간색, 파란색 고르는것은 항상 매트릭스가 생각나 두개의 버튼 n에서 m을 만들기 위한 최소 버튼 클릭수를 계산하는 문제 내 마음대로 번역 바시야(Vasya)는 신기한 장치를 찾았습니다. 패널의 앞부분은 빨간 버튼, 파란 버튼, 양의 정수를 보여주는 디스플레이가 있습니다. 1) 빨간 버튼을 누르면, 장치는 디스플레이의 숫자에 2를 곱합니...
백준 16236 아기 상어
skyepodium

백준 16236 아기 상어

2019년 7월 21일0개의 댓글
문제 아기 상어가 물고기를 잡아 먹을 수 있는 시간을 구하는 문제 ~으아 문제가 정말 길어요~ 1. n 공간의 크기 (2 = n = 20) 2. 지도의 크기 n * n, (1 * 1 에는 최대 물고기가 1마리 있습니다.) 3. 상어, 물고기 크기는 모두 자연수입니다. 4. 지도 정보 1) 상어 - 위치 - 상어의 위치는 숫자 9로 표시...
doontagi

그래프 BFS 문제2 - 어린이날

2019년 7월 18일0개의 댓글
image.png 문제 파악 답이 될 수 있는 숫자를 구성하는 숫자가 정해져 있으므로, 답을 구성할 수 있는 숫자들을 그래프의 노드로 보고 BFS로 탐색하면서 최소가 되는 답을 찾을 수 있지 않을까 생각했다. 그러나 문제점은 이런 방식으로 탐색할 경우 답이 존재하지 않는 경우 종료하는 지점을 설정하는 것이 불가능 하다는 것이다. 문제 풀...
doontagi

그래프 - BFS 문제1 Sorting game

2019년 7월 17일0개의 댓글
image.png 문제 파악 배열의 원소를 최소 횟수로 뒤집어 정렬된 배열을 만드는 문제이다. 배열의 최대 크기가 8이고 배열이 한 번 뒤집힐 때마다 다른 상태가 되며 정렬된 상태로 나아가야 된다는 점에서 착안해 배열의 현재 순서를 string으로 나타내 그래프의 노드로 표현하려고 했다. 이 과정에서 그래프의 순서를 뒤집는 경우의 수 를 따지면서...
doontagi

그래프 - BFS

2019년 7월 17일0개의 댓글
BFS란 BFS 너비 우선 탐색이란 그래프의 탐색 알고리즘 중 한 가지이다. 너비 우선 탐색은 깊이 우선 탐색과 그래프 탐색 방식의 두 축을 이루는데, 깊이 우선 탐색이 더 이상 경로가 없을 때 까지 계속 한 방향으로 들어가는 것과 달리 시작점과 가까운 노드부터 탐색하는 방식이다. BFS의 구현 너비 우선 탐색 과정 중 새로운 노드를 발견하면 ...
백준 17142 연구소3
skyepodium

백준 17142 연구소3

2019년 4월 20일0개의 댓글
문제 - 연구소의 지도가 주어집니다. (0 빈칸, 1 벽, 2 바이러스) - 전체 바이러스 중에서 m개의 바이러스만 활성화 시킵니다. - 바이러스는 인접한 4방향(위쪽, 오른쪽, 아래쪽, 왼쪽)으로만 이동 가능하며 빈칸만 지날 수 있습니다. - 비활성화 바이러스는 활성화 바이러스를 만나면 활성화 상태가 됩니다. - 지도의 빈칸에 모든 바이러스가 퍼지는 최소...
백준 1068 트리
skyepodium

백준 1068 트리

2019년 3월 3일0개의 댓글
문제 - 첫재 줄에 n이 주어집니다. 정점의 개수가 n개인 트리이며, 트리의 정점은 0번부터 n-1까지 입니다. - 둘째 줄에 각 정점의 부모 정점의 정보가 주어집니다. (-1이면 루트 노드 입니다.) - 셋째 줄에 지울 노드 한개가 주어집니다. -n(1 = n = 50) 정점의 수 - 시간 제한 2초 - 문제 링크 - 접근 과정 1. 탐색 ...
백준 3055 탈출
skyepodium

백준 3055 탈출

2019년 2월 21일0개의 댓글
문제 - 지도가 주어집니다. 1) S 시작점, 2) D 도착점, 3) . 빈칸, 4) X 돌 , 5) * 물 - 시작점에서 도착점까지 인접한 4방향으로 빈칸을 통해서 이동할 수 있습니다. - 물은 매분마다 인접한 4방향으로 빈칸으로 확장합니다. - 다음 이동할 빈 칸에 물이 차오른다면 이동할 수 없습니다. - 시작점에서 도착점으로 이동할 수 있는 최소 시간...
백준 1963 소수 경로
skyepodium

백준 1963 소수 경로

2019년 2월 21일0개의 댓글
문제 - 입력으로 4자리 소수 두개 A, B가 주어집니다. - 1) 소수 A의 4자리 중에서 한 자리만 바꿔서 다음 소수를 만들 수 있습니다. - 2) 다음 소수에서 또 한자리를 바꿔서 다다음 소수를 만들 수 있습니다. - 소수 A에서 B를 만들 수 있는 최소 변경 횟수를 구하시오. - (A에서 B를 만들 수 없을때는 Impossible를 출력하세요) - ...
알고스팟 ORIVIRUS 오리 독감
skyepodium

알고스팟 ORIVIRUS 오리 독감

2019년 2월 10일0개의 댓글
문제 - 1 ~ n 번재 사람의 관계 정보를 인접행렬로 주어집니다. 두 사람이 연결되어 있으면 서로 친구입니다. - m개의 시나리오가 있고, 각 시나리오의 최초 감염자는 2명씩 주어집니다. - i번째 사람의 친구들 중 감염자가 2명이상이면 i번째 사람도 감염자가 됩니다. - 각 시나리오 마다 총 감염자의 수를 구하시오. -n(1 = n = 500) 학생 수...
백준 5567 결혼식
skyepodium

백준 5567 결혼식

2019년 2월 6일0개의 댓글
문제 - 상근이와 친구들의 관계를 그래프로 나타내었을 때, 시작점(상근이)으로부터 최단거리가 2이하인 정점의 개수를 구하시오. -2 = n = 500 (n은 정점의 개수), 1= m = 10000 (m은 간선의 개수) - 시간 제한 1초 - 문제 링크 - 접근 과정 1. 그래프 - 상근이와 친구들의 관계를 양방향 그래프로 설계합니다.(문제에서 ...