본문 바로가기

BFS11

[C++/프로그래머스] 경주로 건설 (2020 카카오 인턴십) 문제 https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 문제를 요약하자면, 정사각형 모양의 board에서 (0, 0)에서 (N-1, N-.. 2022. 1. 18.

[C++/프로그래머스] 단어 변환 문제 https://programmers.co.kr/learn/courses/30/lessons/43163 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 .. 2022. 1. 12.

[백준/C++] 1941. 소문난 칠공주 문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과감히.. 2021. 8. 24.

[C++/백준] 17244. 아맞다우산 문제 https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 2차원 맵에서, 출발에서 도착점으로 가는데, X로 표시된 필요한 물건들을 모두 챙겨서 나가는 최소 이동거리를 구하는 문제이다. 풀이 그래프상에서 최소 이동 횟수를 구하는 문제이기 때문에 BFS를 이용했다. 그리고, 그래프상에 X가 있는 지점을 모두 방문하는게 조건이기 때문에 X방문체크를 어떻게 할지 고민하다가, X가 최대 5개라고 해서 길이 5짜리 비트마스크를 이용해서 방문체크를 해주.. 2021. 8. 3.

[백준/C++] 1600. 말이 되고픈 원숭이 문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 [BFS + 구조체] BFS를 이용해서 풀면 되는 문제였다. 일반적인 BFS에서, 상하좌우로 이동하는 것만을 고려했다면, 이 문제에서는 "말 처럼 이동할 수 있는 경우"도 고려해서 BFS를 돌려주면 되는 문제였다. 다만 "말 처럼 움직일 수 있는 횟수"가 K번으로 정해져있으므로, 남은 횟수 k도 큐에 넣어 확인해주었다. * 처음에 visited배열을 2차원으로 만들어서 .. 2021. 6. 29.

[백준/C++] 1194. 달이 차오른다, 가자 문제 https://www.acmicpc.net/problem/1194 0에서 출발하여 1까지 갈 수 있는 최단경로를 구하는 문제이다. #은 지나갈 수 없고, a~f는 열쇠, A~F는 문이며 각 문을 지나기 위해서는 해당하는 소문자 열쇠를 가지고 있어야한다. 풀이 열쇠와 문이라는 요소가 추가되기는 했지만, 기본적으로는 BFS를 이용하여 최단경로를 찾는 문제이다. 구조체를 만들어서 BFS를 돌리는것 까지는 비교적으로 금방 할 수 있었는데, 메모리초과가 났다. visited배열을 visited[2][2][2][2][2][2][51][51]로 만들고, 구조체에 6칸짜리 vector를 넣어서 그런 것 같았다. 검색을 해보니, 열쇠 관련 부분을 "비트마스킹"으로 해결해야 하는 문제였다. 따라서 visited배열을.. 2021. 6. 2.

[백준/C++] 9019. DSLR 문제 https://www.acmicpc.net/problem/9019 풀이 BFS를 이용했다. 가능한 경우의 수가 0 ~ 9999 까지 였기 때문에, 10000크기의 visited 배열을 만들어 이용했다. 처음에 L과 R을 숫자를 String으로 바꾸어서 만드는 방식으로 해서 시간초과가 나왔다. 굉장히 사소한 부분이라고 생각했는데, 테스트케이스를 많이 집어넣을 수 있는 방식이라서 시간초과가 난 것 같다. 그리고 main에 cin, cout 입출력 시간을 줄이기 위한 코드를 추가했더니 시간이 아주 조금 더 줄었다. 코드 #include #include #include using namespace std; #define MAX 10000 bool visited[MAX]; string BFS(int A, i.. 2021. 5. 26.

[백준/C++] 1525. 퍼즐 문제 https://www.acmicpc.net/problem/1525 풀이 BFS를 이용해서 풀었다. 그리고 구조체를 만들어, 큐에 구조체를 넣는 방식으로 BFS를 구현했다. 첫 번째 시도 방문체크를 876543211 크기의 배열 이용 구조체 안에 int 3개(r, c, count), 3x3 vector 한 개 → 메모리 초과 ! 두 번째 시도 구조체에 너무 많은 것들이 들어있는게 문제인가 싶어서, 구조체안에 int 1개, string 1개만 넣도록 했다. → 메모리 초과 ! 최종 시도 방문 체크를 string set을 이용해서 했다. 876543211크기의 visited 배열을 만든 것 자체가 메모리 초과의 원인인 것 같았다. 코드 #include #include #include #include #i.. 2021. 5. 26.

[백준/C++] 2589. 보물섬 문제 https://www.acmicpc.net/problem/2589 육지와 바다로 이루어진 nxm 맵에서 육지에서 시작해서, 바다를 거치지 않고 갈 수 있는 가장 먼 육지까지의 최단경로를 구하는 문제이다. 풀이 BFS를 이용해서 풀었다! 또한, 모든 육지가 시작점이 될 수 있기 때문에 완전탐색이기도 하다. 모든 육지에서 BFS를 돌려서, 다른 육지까지의 최단경로를 모두 구해서 그 중에 최댓값을 출력했다. 코드 #include #include using namespace std; int dr[4] = { -1,1,0,0 }; int dc[4] = { 0,0,-1,1 }; int map[52][52] = { 0, }; int cache[52][52] = { 0, }; int max_dist = 0; vo.. 2021. 5. 19.

이전 1 2 다음

티스토리툴바