BFS

[프로그래머스 level 3] 네트워크 (C++)

BFS 또는 DFS로 풀 수 있는 문제이다. 위 그래프는 2개로 나눌 수 있다. 위 그래프는 하나로 연결된 하나의 그래프이다. 모든 노드는 BFS 탐색의 시작점이 될 수 있다. BFS를 통해 방문한 노드는 방문 기록을 남기게 되고, 시작점이 되지 못한다. 시작점이 없을 때까지 BFS를 수행하고, 문제의 답은 BFS를 수행한 횟수가 된다. 개인적으로 이 문제를 비롯한 기본 bfs, dfs문제들이 왜 level 3인지 이해가 되지 않는다. 최종 코드 #include #include #include using namespace std; vector adj[201]; bool visited[201]; void bfs(int start){ queue que; que.push(start); visited[start..

[백준 14867] 물통 (C++)

14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a B로 물 이동 B->A로 물이동 현재 상태로부터 총 6가지의 상태로 변화할 수 있다. 하지만 bfs의 특성상 다음 상태가 이미 나온적..

[백준 5547] 일루미네이션 (C++)

5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net BFS 구현 문제이다 위 그림에서 2,3 좌표는 비어있는데 건물에 둘러싸인 '내부 공간'이다. 건물이 좌표 바깥이나 외부 공간과 맞닿아 있다면 답을 +1 해주면 되는데, 내부 공간이라는 변수 때문에 단순한 bfs로는 풀리지 않는다. 따라서 빈 공간이 내부 공간인지, 외부 공간인지를 미리 판단 해 놓아야 한다. 그걸 어떻게 판단하는가? 하나 이상으로 이어진 외부 공간은 좌표 바깥 부분과 맞닿아있다. 따라서 좌표의 경계선에 위치한 빈 ..

[프로그래머스] level2 거리두기 확인하기

단순 bfs, dfs 문제이다. 최대 2칸까지 이동할 수 있다. 다음 칸이 'X'인 경우 이동하지 않는다. 다음 칸이 'P'인 경우 거리두기가 지켜지지 않은 것이므로 false를 반환한다. bfs로 풀면 queue의 각 원소가 현재 몇 칸 움직인 상태인지 저장해두는 작업이 필요해서 queue를 구성하는 struct를 새로 구현하게 되었다. #include #include #include #include #define pii pair using namespace std; struct Info{ pii now; int cnt; }; int dr[4] = {0, 0, 1, -1}; int dc[4] = {1, -1, 0, 0}; int Map[6][6]; bool check(int r, int c){ queu..

[백준 1726] 로봇 (c++)

1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 오랜만에 푼 알고리즘 문제 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다. 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다. 두 가지 조건을 만족하며 출발 로봇이 도착지점의 상태와 같아질 때까지 이동시키는 프로그램을 구현하면된다. 나는 K칸 만큼 움직일 때 갈 수 없는 모든 조건에 break를 걸어주어서 많이 틀렸다. 벽에 막혀서 갈 수 없는 경우에만 ..

[백준 1941] 소문난 칠공주 (C++)

1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 처음에 단순 dfs로 갔다가 ㅓㅏㅗㅜ 모양으로 탐색이 불가능해서 바로 접었다. bfs로 다시 도전하는데 정점간의 상태정보를 공유할 수가 없어서 방법을 생각하다가 모든 경우의 수가 최대 25C7 = 48만으로 충분히 탐색 가능함을 깨닫고 dfs를 사용해서 상태 정보를 기록하고 구한 상태들이 서로 이어져 있는 경우를 찾는 방식으로 시도를 했다. 2차원 배열을 1차원 배열로 바꿔서 편하게 백트래킹을 할 수도 있었지만 굳이 내가 2차원 배열을 유지하면서 백트래킹을 해보려는..

[백준 1948] 임계경로 (C++)

1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 단방향 그래프(DAG)임을 유의 특정 도시에서 모두 만나는데 걸리는 시간은 시작도시에서 특정 도시까지 가는데 걸리는 모든 시간 중 최댓값이 된다. 따라서 BFS를 통해 모든 정점에 대해 걸리는 시간 값을 구할 수 있다. 도착 정점까지 쉬지 않고 달려야 하는 사람이 지나는 도로의 개수의 의미는 도착 정점을 시작점으로 해서 되돌아 갈 때, '도착 정점까지 가는데 걸리는 시간 - 도착 정점을 시작으로 특정 정점까지 가는데 걸리는 시간 = 시..

[백준 15591] MooTube(Silver) (C++)

15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net N과 Q가 각각 최대 5000이므로 주어지는 쿼리마다 매번 bfs를 수행해도 시간에 늦지 않을 것이라고 생각했다. 시작점에서 bfs를 수행하면서 다음 영상과의 유사도(USADO)가 K보다 작은 경우 다음 영상은 추천되지 않는다고 생각하면 편하다. K보다 큰 경우에만 다음 영상의 번호를 큐에 넣으면서 bfs를 수행하고 그 수를 카운팅을 해준다면 매 쿼리마다 답을 구할 수 있게 된다. 1 2 3 4 5 6 7 8 9..

[백준 1525] 퍼즐 (C++)

1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net BFS, 비트마스킹 3x3 크기의 퍼즐은 각 칸마다 0~8까지의 숫자가 들어간다는 것을 이용해서 하나의 숫자당 4개의 비트를 사용. long long 타입에서 총 36개의 비트를 사용해 3x3 퍼즐의 정보를 저장하도록 했다. 위 퍼즐에서 0의 위치는 3행 3열에 있다. 따라서 32번째 비트~35번째 비트 공간이 해당 칸을 저장하게된다. 그리고 특정 칸에 위치한 숫자를 알아내기 위한 mask로서 Checker배열을 설정했다. BFS를 수행하면서 매번 0의 위치를 찾아준다. 0의 위치를 찾았다면 0이 갈 수 있는 4방향을 모두 탐색해본다. 범..

[백준 17472] 다리 만들기 2 (C++)

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net BFS, 최소 스패닝 트리 BFS를 통해서 각 칸마다 섬의 번호를 지정해서 섬을 구분한다. 모든 섬과 섬 사이의 거리를 구한다. 서로 이어지지 않은 섬은 거리를 INF로 한다. 여기까지 사전작업을 마쳤으면 모든 섬을 연결하는 최소 거리를 구하면 된다. 모든 노드를 연결하는 최단거리를 구하는 알고리즘은 최소 스패닝 트리임을 알 수 있다. 2번 과정에서 얻은 섬 간의 거리는 양방향이었으므로 중복되는 구간은 제외하고 새로운 벡터에 넣어준다. 거리를..