# BFS

1141개의 포스트
post-thumbnail

17472 다리 만들기 2

굉장히 복합적인 시뮬레이션 문제이다. 다양한 알고리즘을 연습하기에 좋다.https://www.acmicpc.net/problem/17472우선 각각의 섬을 구분할 수 있어야 하므로 섬에 번호를 붙여주어야 한다.반복문을 돌면서 만약 방문하지 않은 섬을 만나면 b

약 22시간 전
·
0개의 댓글

[알고리즘 풀이 분석] BOJ 4179 불!

오늘 두번째로 풀어본 문제는 BOJ 4179 불! 이다. 건방지게 덤볐다가 생각보다 겁나 오래 걸렸다 ㅎ,, 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는

약 22시간 전
·
0개의 댓글

[알고리즘 풀이 분석] BOJ 13549 숨바꼭질 3

오늘 풀어본 문제는 BOJ 13549 숨바꼭질 3 이다. 골드 5 단계 문제이고 특별할 것 없는 그래프 탐색 문제인 것 같지만 주의할 점이 있었다! 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤

어제
·
0개의 댓글
post-thumbnail

[BOJ]벽 부수고 이동하기 3.java

이 문제 역시 벽 부수고 이동하기 2와 비슷하다. 다만 고려사항이 더 추가되었다 .제자리에서 대기할수 있다는 것과 낮에만 벽을 부술수 있다는 것. 이때 불필요한 움직임을 없애주어야지만 시간초과가 나지 않는다 따라서 벽을 부술수 없는 낮에만 제자리에서 대기를 하고 벽을

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

[BOJ]14442 벽 부수고 이동하기 2.java

일반적인 BFS문제와 비슷하다 .. 그러나 벽을 몇개 부쉇는지의 여부에 따라 방문배열을 달리 해주어야 하고 체크도 따로 해주어야 한다.

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

[BOJ]12851 숨바꼭질2.java

이 문제는 숨바꼭질을 변형한 문제이지만 접근방식이 약간 다르다 .똑같이 BFS로 풀었다. 하지만 queue에 추가해주는 조건이 조금 까다롭다. 나는 동일한 횟수로 접근하는 방법을 구하기 위해서 방문을 했어도 동일한 시간에 접근을 했다면 queue에 추가해주는 방식을 사

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

[BOJ]13549 숨바꼭질3.java

숨바꼭질1을 변형한 문제이다. 위치가 2가 될때는 시간이 소모되지 않는 차이점이 있다. 따라서 시간초과가 걸리지 않는 2를 먼저 탐색해주어야 한다. 즉. 탐색 순서에 따라 정답여부가 갈린다. 이 문제에서 주의해야 할점이다.

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

[BOJ]16953 A → B.java

BFS로 풀면 간단히 풀리는 문제이다. int형 범위를 넘을 수 있으니 long타입을 사용하도록 하자.

2일 전
·
0개의 댓글

백준 2206번: 벽 부수고 이동하기

백준 2206번: 벽 부수고 이동하기맨 처음 생각했던 방법은 모든 벽 (1)을 길(0)으로 하나씩 바꿔보고 BFS를 하는 방식이었는데 벽의 최대 개수가 NM개이기 때문에 시간복잡도가 O(N^2M^2)가 되어 풀 수 없었다.모든 벽을 부숴보면서 풀 수 없기 때문에 길을

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

BOJ: 14502번 - 연구소 (feat. C++)

백준 14502번 연구소를 풀어보았다. 시뮬레이션을 곁들인 백트래킹, BFS, DFS 문제인데 감만 잡으면 굉장히 쉬운 문제였다. 감을 못잡아서 문제지시뮬레이션 문제라고 느낀 이유는 문제가 시키는 대로 하면 해결의 실마리가 보이기 때문이다. 해결 방법을 크게 생각해보면

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

백준 2206번 벽 부수고 이동하기 파이썬

간단한 bfs 문제이다.' 벽을 뚫고 갈 수 있다.'이게 포인트 인데처음에는 드릴을 뚫었나 안뚫었나 이것만 생각해서visited 에는 count값, 오는데 걸린 횟수를 넣고0 , 1 로 뚫고왔는지 안뚫고 왔는지를 체크했다.이렇게 하니 11%에서 막혔다.그래서 visit

4일 전
·
0개의 댓글

BOJ 16953(A ->B)

2를 곱한다.1을 수의 가장 오른쪽에 추가한다.처음에 문제를 봤을때 바로 BFS가 떠올라서 내심 알고리즘 실력이 상승했구나 기뻤다.하지만, 기쁜 건 순식간에 슬픔으로 됐다. 😅처음엔 "queue에 A에 연산한 결과들을 넣어두고 B가 될 때까지 반복한다" 라고 로직을

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

백준 13549 파이썬

백준 13549

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

백준 12851 파이썬

백준 12851

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

[BOJ] 백준 2660번 회장뽑기 (Python)

백준 2660번 회장뽑기 [ 골드 5 ] 풀이 python

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

[ BOJ / C++ ] 15591번 MooTube (Silver)

이번 문제는 BFS를 통한 그래프 탐색으로 해결하였다. 문제를 이해하는데 조금 오래 걸렸던 것 같다.매 사이클마다 방문한 영상인지 체크하기 위한 visited 배열을 선언한다.영상은 vector 배열로 선언하여 각 영상에서 추천되는 영상을 저장한다.영상 간의 연결은 양

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

[BOJ] 5567. 결혼식

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕

2021년 9월 19일
·
0개의 댓글
post-thumbnail

BOJ 13549: 숨바꼭질 3

✔ 문제 링크 BOJ 13549: 숨바꼭질 3 > ### ✔ 문제해결전략 >> - 그래프 탐색 >> - 1차원에서의 BFS(Breadth First Search) > ### ✔ 해결과정 >> - BOJ 1697: 숨바꼭질에서 *2는 0초 만에 가능한 것으로 바뀌었

2021년 9월 18일
·
3개의 댓글
post-thumbnail

BFS를 활용한 최단 거리 계산 in C++

disx : 위치x에 있을때, 몇번 움직였는지 기록ex)5 14

2021년 9월 18일
·
0개의 댓글
post-thumbnail

BFS를 활용한, 방향 그래프 최단거리 in C++

1. 한 정점에서 출발하여, 방향 그래프내에서 각 정점까지 최단거리를 구하는 코드 출발하는 정점은 1번 정점으로 한다. #include #include using namespace std; int n, m; int ch[101], dis[101]; vector gra

2021년 9월 18일
·
0개의 댓글