본문 바로가기

Problem/BFS

[C/C++] BOJ 5014 :: 스타트링크 BOJ 5014 :: 스타트링크 문제 링크 : https://www.acmicpc.net/problem/5014 나의 풀이 예외조건을 제외하고 넓이우선탐색으로 최소 버튼 수를 도출한다. * 예외조건* 1) 현재층 = 도착층일 때, 0 출력 2) 현재층 > 도착층인데 아래층으로 갈 수 없을 때3) 현재층 < 도착층인데 윗층으로 갈 수 없을 때4) 윗층과 아래층 모두 갈 수 없을 때 use the stairs 출력 bfs탐색한 후, G에 도착가능할 때, 최소 버튼 수 출력G에 도착가능하지 않을 때, use the stairs 출력 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_5014/BO..
[C/C++] BOJ 2251 :: 물통 BOJ 2251 :: 물통 문제 링크 : https://www.acmicpc.net/problem/2251 나의 풀이 모든 물통에 들어갈 수 있는 물의 양의 상태를 BFS로 탐색해나간다. [총 6가지 경우]A물통에 물이 있으면 => B와 C에 물을 채울 수 있다.B물통에 물이 있으면 => A와 C에 물을 채울 수 있다.C물통에 물이 있으면 => A와 B에 물을 채울 수 있다. [Ex] 가득 채울 수 있는 물의 양이 A, B, C이고현재 들어있는 물의 양이 각 a, b, c 일 때, A물통에 물이 있으면, B와 C에 물을 채울 수 있다.B에 물을 채울 때, 1) B의 물통을 모두 채우고 물이 남는 경우, 각 물의 양의 상태는 a-(B-b), B, c 가 된다.2) B의 물통을 가득 채울 수 없는 경우, 각..
[C/C++] BOJ 11559 :: Puyo Puyo BOJ 11559 :: Puyo Puyo 문제 링크 : https://www.acmicpc.net/problem/11559 나의 풀이 BFS 방식으로 연결된 블록의 개수를 찾는다. 4개 이상 연결되어있으면 그 위치의 map을 모두 '.'로 변경시킨다. 모든 정점에 대한 탐색을 마치면, 한 열마다 queue로 '.'가 아닌 값을 저장한후, 가장 밑 행부터 채워넣음으로써 map을 갱신한다. 내가 실수했던 부분) 1. 원래 항상 하던 방법인 !q.empty() 로 하지 않고 다른 방식으로 하려다 보니 연결된 블록을 찾을 때 while문에서 빠져나가는 오류가 발생..2. 문제를 제대로 안읽어서 삭제될 블록을 하나 찾을때마다 ans를 갱신함..3. index,, 0~12미만이아니라 11~0까지로 구현하는 것에서 ..
[C/C++] BOJ 16236 :: 아기 상어 BOJ 16236 :: 아기 상어 문제 링크 : https://www.acmicpc.net/problem/16236 나의 풀이 아기상어가 먹은 상어의 마리 수에 따른 3차원 visited배열로 방문여부를 확인.아기상어의 위치, 크기, 크기 갱신을 위해 몇 마리 먹었는지 보여주는 변수, 누적하여 먹은 마리 수, 걸린 시간, 먹을 수 있는 상어인지 여부의 구조체로 아기상어의 노드를 저장한다. - 먹을 수 있는 상어가 1마리 이상일 경우, x, y 좌표 오름차순으로 sorting하여 가장 맨 앞의 값만 queue에 다시 넣어준다.이 때, 크기, 크기 갱신을 위해 몇 마리 먹었는지 보여주는 변수, 누적하여 먹은 마리 수, 먹을 수 있는 상어인지 여부를 갱신한다.답이되는 걸린시간도 ans에 갱신한다. 매우 지저분..
[C/C++] BOJ 3/2 코딩테스트 대비 모의고사 B번 - Baaaaaaaaaduk2 (Easy) BOJ 3/2 코딩테스트 대비 모의고사 B번 - Baaaaaaaaaduk2 (Easy) 나의 풀이 바둑판의 값이 0인 것들의 위치를 순차적으로 벡터 v에 저장한다. 벡터를 돌면서 0의 위치의 값을 1로 바꾸고 2개가 바뀌었을 때, 죽일 수 있는 상대 돌의 개수를 센다. bfs방식으로 바둑판의 값이 2인 곳의 탐색을 시작하면서 상하좌우에 2가 있으면 죽일 수 있는 돌의 개수를 1 증가시킨다. 상하좌우에 0이 있으면 탐색을 마쳤을 때, 죽일 수 있는 돌의 개수를 갱신하지 않는다. 모든 탐색을 마친 후, 이전 ans와 비교하여 죽일 수 있는 돌의 개수가 더 많을 때 갱신한다. 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Dal..
[C/C++] BOJ 16234 :: 인구 이동 BOJ 16234 :: 인구 이동 문제 링크 : https://www.acmicpc.net/problem/16234 나의 풀이 flag를 여러 군데에 사용하다 보니 코드가 좀 지저분한 감이 있긴 하다 ㅠㅠ 1. 배열을 방문하지 않았을 때, 너비 우선 탐색으로 인구 이동이 가능한 지역끼리 clustering을 한다. 2. 각 그룹은 숫자 1, 2, 3.. 으로 지정하고, 그에 맞는 인구 수를 계산하여 일차원 배열 group에 저장해 둔다. 3. 전체 배열의 탐색을 마치면, clustering 된 그룹의 인구 수를 미리 계산해 둔 group의 각 값으로 대체한다. 4. 탐색한 횟수를 증가시킨다. 5. 종료 조건 : 탐색 시, clustering이 한번도 되지 않았다면, flag가 변화하지 않아 종료. 나의 ..
[C/C++] BOJ 2234 :: 성곽 BOJ 2234 :: 성곽 문제 링크 : https://www.acmicpc.net/problem/2234 나의 풀이 - 비트연산으로 이웃한 칸에 갈 수 있는지 확인하면서 그룹을 짓는다. if (castle[x][y] & (1
[C/C++] BOJ 1938 :: 통나무 옮기기 BOJ 1938 :: 통나무 옮기기 문제 링크 : https://www.acmicpc.net/problem/1938 나의 풀이 - 통나무 중간 부분 좌표와 방향이 있으면 통나무의 모양을 알 수 있다. => 통나무의 중간 부분과 방향으로 탐색을 진행한다. 1. 상하좌우 방향에 따라 상하좌우로 움직였을 때, 지도를 벗어나면 continue2. 움직일 수 없는 공간이면 continue3. 이미 방문한 지점이면 continue그 외에는 queue에 넣는다. 1. 상하좌우에 대각선을 포함하여 8방향이 지도를 벗어나면 break2. 움직일 수 없는 공간이면 break3. 방문하지 않은 지점이면 queue에 넣는다. 처음 코드를 제출했을 때 실수를 했는데 회전 탐색시 방문 여부를 판단할 때이다. 조건문 안에서 조건문..

티스토리툴바