# BFS

604개의 포스트
post-thumbnail

백준 2146 다리만들기

문제링크 https://www.acmicpc.net/problem/2146 문제 풀이 섬과 섬의 구분을 위해 각 섬에서 bfs를 이용해 넘버링을 해주었습니다. 모든 섬에 대해 다시 bfs를 실행해 다른 섬에 도착하는 최단 거리를 측정 하였습니다. 시행착오 없었습니다. 코드 후기

약 6시간 전
·
0개의 댓글
post-thumbnail

[프로그래머스] LV.3 단어변환 (JS)

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.예를 들어 begin이 "hit", target가 "cog", words가 "hot"

어제
·
0개의 댓글
post-thumbnail

[BOJ]16959. 체스판여행

BOJ 16959 문제 바로가기문제의 저작권은 백준 온라인저지에 있습니다.처음 시작하는 좌표가 0,0이라는 보장이없다는것을 모르고 틀렸었다,,, 이점 잘 확인하자

어제
·
0개의 댓글
post-thumbnail

BOJ 19238 : 스타트 택시 - C++

주의board\[]\[]와 cost\[]\[]를 인덱스 1~N까지 사용하는데 초기화를 0부터 함\--> 아래처럼 해야 1부터 N까지 초기화가 된다for(int i=1;i<=N;i++) fill(cost\[i]+1, cost\[i]+N+1, -1);예외처리고객을 태

2일 전
·
0개의 댓글
post-thumbnail

리스트와 매트릭스를 이용한 BFS 접근방식

방향이 있는(양방향) 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.각 정점(vertex)의 종류와 개수를 확인한다.연결관계를 리스트나 매트릭스 방식으로 지정해준다.리스트: {0:\[1], 1:\[0], 2:\[3]

2일 전
·
0개의 댓글

백준 1463번 ) 1로 만들기

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의

3일 전
·
0개의 댓글
post-thumbnail

백준 2638 치즈

문제링크 https://www.acmicpc.net/problem/2638 문제 키포인트 가장자리는 치즈가 놓이지 않으므로 가장자리에서 부터 BFS나 DFS를 실행해줍니다. (아래 코드는 bfs 이용) 0인 부분(치즈가 없는 영역)은 방문하지 않았다면 큐에 넣어주고 1인 부분(치즈가 있는 영역) 은 큐에 넣지 않고 해당 좌표의 값을 1증가 시켜줍니다. 큐...

4일 전
·
0개의 댓글

[JS] Q15 특정 거리의 도시 찾기

어떤 나라에는 1~N번까지의 도시와 M개의 단방향 도로가 존재합니다. 모든 도로의 거리는 1입니다. 이때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하세요. 또한 출발 도시 X에서

4일 전
·
0개의 댓글

[JS] 미로 탈출

동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하여 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로,

5일 전
·
0개의 댓글

DFS와 BFS

DFS란?BFS란?그래프에서 적용된 모습차이점 비교DFS는 Depth-First Search의 약자로 깊이 우선 탐색이란 뜻입니다.트리에서 사용한다면 다음과 같은 순서를 가집니다.선택 가능한 자식 노드가 없을 때까지 자식 노드를 우선적으로 선택합니다.모든 노드를 탐색해

5일 전
·
0개의 댓글

"순위" 문제 풀이

요즘 Jest와 다른 공부들을 하다보니까 시간이 모자라 하루에 한 문제씩 풀지 못하고 놓치는 경우가 생기고 있다... ㅠ ㅠ시간관리를 잘 하지 못한 내 핑계지만 놓친만큼 주말에 최대한 맞춰야겠다.이번 문제는 처음에는 어떻게 이거를 그래프로 풀지 싶었는데 고민하다보니까

5일 전
·
0개의 댓글

[JS] DFS/BFS

DFS/BFS JavaScript 소스 코드

5일 전
·
0개의 댓글
post-thumbnail

BOJ 17142 : 연구소 3 - C++

핵심: next_permutation을 이용해서 전체 virus개수 중 M개를 선택하는 조합을 모두에 대해 전부 바이러스를 퍼뜨리는 경우 중 최소값을 기록시간복잡도 최대 10개의 바이러스 중 5개를 선택하는 수이기 때문에 252가지 경우를 가진다252가지 경우에 대해

6일 전
·
0개의 댓글
post-thumbnail

백준 - 영역 구하기 [2583]

백준 - 영역 구하기 [2583]

6일 전
·
0개의 댓글
post-thumbnail

BOJ 16236 : 아기상어 - C++

로직shark의 좌표를 시작으로 BFS를 수행해서 가장 가까운 좌표를 찾는다ans를 증가시키고 shark를 update!느낀 것 : 문제의 조건을 정확하게 파악하지 못해서 시간이 오래걸렸기 때문에 정신을 차려야 한다

6일 전
·
0개의 댓글
post-thumbnail

2206 벽부수고이동하기

문제링크현재상태를 계속해서 큐에 집어넣어주고 벽을 부쉈는지에대한 visit배열을 한차원 늘려서 확인해준다.이외의 중요팁들은 백준 게시판에서 글을 가져와보았다.

7일 전
·
0개의 댓글