BFS
[BaekJoon] 백준 2638번 치즈
[BaekJoon] 백준 2638번 치즈 🎈문제 https://www.acmicpc.net/problem/2638 💬설명 bfs로 풀었다. 과정 bfs를 이용해 [0, 0]부터 시작해서 (치즈 내부에 있지 않은) 모든 빈공간을 탐색한다. 이때 치즈가 있는 곳의 좌표를 마주칠 때마다 개수를 카운트 해놓는다. 카운트 해놓은 개수로 2 이상인 치즈는 지운다. 1-2를 반복하고 만약 치즈가 다 녹아 없어진 경우 횟수를 출력한다. 👩💻코드 # BaekJoon2638.py from collections import deque N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] dx = [0, 0, 1, ..
[BaekJoon] 백준 1389번 케빈 베이컨의 6단계 법칙
[BaekJoon] 백준 1389번 케빈 베이컨의 6단계 법칙 문제: https://www.acmicpc.net/problem/1389 문제를 보고 친구 관계가 연결되어 있고, 관계를 하나하나 따라 들어가 몇단계인지 찾는다는 부분에서 이거 뭔가 탐색 문제일 것 같은데..! 라는 생각이 들었다. 이어서 최단 경로의 단계를 찾는다는 부분에서 이건 bfs다 라는 생각으로 이어졌다. 어떤 유형의 문제인지 알았으니 이제 입력 받은 데이터를 어떻게 넣어서 bfs를 통해 풀면 될것 같은데, 어떤 자료구조로 넣지? 생각하다가 그래프의 두가지 표현 방식인 1) 인접 리스트(1: 2, 4, 5 / 2: 1, 5 / ...) 2) 인접 행렬(arr[i][j]로 표현)이 떠올랐다. 그중에서 나는 특정 점에 연결된 점들을 찾는..
[BaekJoon] 백준 13549번 숨바꼭질 3
[BaekJoon] 백준 13549번 숨바꼭질 3 문제: https://www.acmicpc.net/problem/13549 내코드 - 기존의 bfs랑 약간 다른 문제 - 그렇게 쉽지도 어렵지도 않은 문제 - 전에 풀었던 [BaekJoon] 백준 1697번 숨바꼭질 문제와 내용은 비슷하지만 priority queue를 이용해서 순간이동 하는 경우를 따로 처리해줘야하는 점이 달랐다. - 순간이동하는 경우 시간이 소요되지 않기 때문에 고려해서 priority queue를 사용해주면 된다. #include #include #include #define MAXNUM 100001 using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(..
[BaekJoon] 백준 6593번 상범 빌딩
[BaekJoon] 백준 6593번 상범 빌딩 문제: https://www.acmicpc.net/problem/6593 내코드 - 간단한 bfs 문제 - 다른 점은 3차원 배열을 이용한다는 것. - x, y, z 위치만 헷갈리지 말고 맞춰주자. #include #include #include #define MAXNUM 30 using namespace std; int dx[] = { 0, 0, 1, -1, 0, 0 }; int dy[] = { 1, -1, 0, 0, 0, 0 }; int dz[] = { 0, 0, 0, 0, 1, -1 }; int main(void) { ios::sync_with_stdio(false); cin.tie(0); int l, r, c; cin >> l >> r >> c; ch..
[BaekJoon] 백준 2146번 다리 만들기
[BaekJoon] 백준 2146번 다리 만들기 문제: https://www.acmicpc.net/problem/2146 내코드 - 어렵게 생각했지만 생각보다 간단했던 문제 - bfs 및 dfs로 풀수 있는 문제다. - 알고리즘 1. 각 섬을 bfs로 돌며 1, 2, ... 라벨링 해준다. 즉, map에서 같은 섬은 같은 번호를 가지고 있다. 2. (섬의 개수 - 1)번 만큼 for문을 돌면서 각각의 섬 번호에 대해 bfs_search()함수를 돌려준다. 3. bfs_search() 함수가 1번 섬에 대해 도는 경우를 생각해보자. 3-1. 1번으로 라벨링된 지점을 모두 queue에 넣어준다. 3-2. queue가 빌때까지 상하좌우의 지점에 대해 만약 바다면 push해주는 것을 반복한다. 3-3. 바다가 ..
[BaekJoon] 백준 5427번 불
[BaekJoon] 백준 5427번 불 문제: https://www.acmicpc.net/problem/5427 내코드 - 일단 이문제는 BFS에 기반한 문제다. 기존 bfs문제들과 조금 다르게 풀어야하기 때문에 알고나면 쉽지만 접근하기가 까다로운문제. - BFS : Queue, 너비 우선, push할때 visited = true를 해줘야함 while(qu가 비어있지 않으면){ 1. pop() 2. 인접 노드들 visited = false면 push } - 알고리즘 1. 테스트 케이스가 여러개이므로 사용하는 변수들을 매번 초기화 시켜준다. 2. bfs를 통해 불에 대한 맵을 만든다.(fireTime) 이때 pop을 통해 얻은 칸의 (time + 1)이 인접한 칸의 time보다 작다면 값을 갱신해준다.(따..
[BaekJoon] 백준 2573번 빙산
[BaekJoon] 백준 2573번 빙산 문제: https://www.acmicpc.net/problem/2573 내코드 - BFS/DFS 문제. 인접한 노드들 개수를 세줘야되서 bfs의 재귀로 푸는건 안됬다. 그래서 익숙한 bfs로 풀어줬다. - BFS: Queue, 너비우선, push 할때 visited = true; function bfs(){ 1. pop 2. 인접한 노드들 push } - while문을 돌릴때마다 모든 노드가 0이 되지 않았는지 체크해준다. - while문 안에서 변수들을 초기화 해준후, bfs를 돌려준다. 이때 인접 노드가 0이면 배열 nearNode[x][y]++을 해줘서 인접한 바다노드의 개수를 세준다. - 한 뭉텅이가 끝나면 year확인 후 2보다 크지 않으면 세준 인접한..
[BaekJoon] 백준 2206번 벽 부수고 이동하기
[BaekJoon] 2206번 벽 부수고 이동하기 문제: https://www.acmicpc.net/problem/2206 내코드 - 정답률이 낮았던 이유가 있는 어려운 문제였다. - 우선, queue에는 좌표값, 거리, 벽을 부쉈는지 아닌지 여부를 넣어주었다. - 벽을 부수고 한 정점에 도착했느냐와 벽을 부수지 않고 도착했느냐가 다르기 때문에 visited배열에 벽을 부수고 왔는지/아닌지를 판별하기 위해 3차원으로 만들어주었다. - 그 다음으로 bfs안에서 다음 칸을 queue에 넣어줄지 말지 생각하는 조건이 4가지로 나뉘어진다. 1. 다음칸이 벽인데 이미 벽을 부순경우 -> 진행 불가. queue에 넣지 않고 지나간다. 2. 다음칸이 벽인데 벽을 아직 안부순경우 ->벽을 부쉈다는 표시를 해주고, qu..