본문 바로가기

Algorithm/BFS

 (63)
(C++) - 백준(BOJ) 13549번 : 숨바꼭질 3 www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net bfs문제였습니다. 풀이방법 1. 순간이동하는데에 cost가 들지 않기 때문에 먼저 10만 이전까지 순간이동을 해보는 것이 유리합니다. 따라서 우선순위를 주기 위해 bfs실행시 priority queue를 사용합니다. 2. bfs를 시행합니다. 시행시 다음 이동할 곳이 범위를 초과하면 안되므로 조건부 push를 해줍니다. Code #include using namespace s..
(C++) - 백준(BOJ) 16928번 : 뱀과 사다리 게임 www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x > m; for(int i = 0; i < n + m; i++){ ..
(C++) - 프로그래머스(고득점 kit - 그래프) : 가장 먼 노드 programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr bfs문제였습니다. 풀이방법 1. 주어진 간선들이 단방향으로 주어지기 때문에 양방향 인접 그래프로 변환해줍니다. 2. 1번 노드에서 시작하여 bfs를 시행합니다. 연결된 노드들까지의 최소거리를 dist배열에 저장합니다. 2. 가장 먼 노드까지의 거리를 저장합니다. 3. 해당거리와 같은 거리의 노드들의 개수를 세줍니다. Code #include #define MAX 0x3f3f3f3f using namespace std; int bfs(vector..
(C++) - 프로그래머스(찾아라 프로그래밍 마에스터) : 게임 맵 최단거리 programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr bfs문제였습니다. 풀이방법 1. bfs 수행 : d배열을 선언해서 0,0에서 출발하여 벽이 아닌 부분을 이동하며 거리를 저장합니다. 2. 도착했을 때 해당 부분의 값이 0이라면 갈수 없으므로 -1을 반환합니다. 아니라면 d[n-1][m-2]를 반환합니다. Code #include using namespace std; us..
(C++) - 백준(BOJ) 1743번 : 음식물 피하기 www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진 www.acmicpc.net bfs문제였습니다. 풀이방법 1. 현재 좌표에 쓰레기가 있고 방문하지 않았다면 쓰레기의 영역 크기를 bfs를 통해 구합니다. 2. 쓰레기 영역들 중 가장 넓은 크기를 출력합니다. Code #include using namespace std; using pii = pair; int dx[] = {0,0,-1,1}; int dy[] = {-1,1,0,0}; int pas..
(C++) - 백준(BOJ) 16236번 : 아기 상어 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net bfs문제였습니다. 풀이방법 1. 먹을 수 있을 때까지 계속 먹이탐색, 이동합니다. 먹을 수 있는 물고기의 거리들을 모두 구합니다. bfs를 이용해 거리정보를 상하좌우 모두 구해줍니다. 지나갈 수 있는 공간은 아기상어보다 작거나 같은 물고기들이 있는 곳이나 0인 부분입니다. 만약 해당 공간의 물고기 크기가 현재 아기 상어의 크기보다 작으면 거리정보와 해당 공간의 행,열 좌표를 vector에 넣어줍니다. ..
(C++) - 백준(BOJ) 16234번 : 인구 이동 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net bfs문제였습니다. 풀이방법 1. 각 국가당 인구를 입력받습니다 2. 이동 할 인구가 없을 때까지 다음을 수행합니다. 2-1. 국경을 열어 연합을 형성했을 때의 인구 지도를 만듭니다. bfs를 통해 인접국가의 차이가 l이상 r이하일 때 같은 연합입니다. 이때 서로 다른 연합의 국가 또한 인접해 있을 수 있습니다. 이 경우 인접은 했으나 차이가 조건에 부합하지 않기 때문에 다른 연합이라고 표시합니다..
(C++) - 백준(BOJ) 2206번 : 벽 부수고 이동하기 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net bfs문제였습니다. 풀이방법 1. 정의하기 : 필요한 정보는 (i,j)의 맵에 도착했을 때 벽의 상태 w(0이면 부수지 않음, 1이면 부서짐) 입니다. 따라서 2차원을 두 가지로 나눠서 생각해야하므로 3차원의 visited배열을 이용해 거리와, 벽의 상태, 방문여부를 확인할 수 있도록 저장합니다. 2. bfs함수 시행 : 두 가지 방식으로 시행됩니다. 2-1. 이동할 수 있는 곳이라면 ..

티스토리툴바