BFS [백준] 2554 : 미로만들기 BFS와 heap을 사용해서 계속 내가 동서남북으로 이동할 수 있는 좌표 중 최소 비용(벽을 뚫는 횟수)을 가지는 좌표로만 이동하게 하는 것이 핵심! 그때 이미 while heap: 안에서 계속 최소 비용을 가지는 좌표로만 이동해주고 있으므로, visited했던 곳을 또 방문할 필요가 없어진다. visited 방문 기록을 남겨주는 이유가 바로 그것! 방문했던 곳을 방문하지 않게 하려고!! 풀... 다시풀문제그래프다익스트라BFS백준코딩테스트BFS 백준 2623 음악프로그램 위상정렬 문제다! 가수들을 그래프의 노드로 생각하고, 입력으로 주어지는 출연 가수의 순서를 단방향성 간선으로 연결해주면 싸이클이 없는 단방향성 그래프가 완성된다 예제 입력의 경우 이렇게 graph와 in_degree가 완성되고 여기서 in_degree는 index의 노드가 몇개의 노드들에게 연결 당했는지(?) 를 나타낸다 in_degree가 0인 노드들을 queue에 삽입하면서 bfs를 통해... algorithmbojTopological SortpythonBFSGraphBFS 백준 16946 벽 부수고 이동하기 4 dfs,bfs를 사용한 풀이 가장 처음 접근은 dfs를 사용했습니다 현재 좌표값이 1일 경우 dfs를 통해서 연결되어 있는 0값들을 카운팅해서 board[i][j]를 수정했습니다 정답은 맞았는데 시간초과가 떴구요 구글에 검색해서 풀이법을 찾아봤습니다 시간을 단축하기 위해 0이 연속적으로 있는 구역들을 그룹핑해서 저장 후 카운팅 bfs를 통해 0의 범위들에게 그룹번호를 지정해줍니다 예를 들어 ... algorithmbojpythonBFSGraphBFS 프로그래머스 카드 짝 맞추기 python cpp 풀이법은 bfs와 dfs를 사용해서 모든 경우의 수를 다 탐색하는 것입니다. 예를 들어서 블록의 종류가 3개라면 이렇게 모든 경우를 다 탐색하는데 이 때 블록의 한쌍이 2개이기 때문에 1번째 블록을 먼저 지우고 2번째 블록을 지우는 경우와 2번째 블록을 지우고 1번째 블록을 지우는 경우까지 전부 생각해서 구현해주면 됩니다 그리고 블록간의 거리는 문제에서 주어진 조건으로 b... DFSalgorithm카카오 기출programmerscpppythonBFSGraphsimulationBFS 백준 [7569] 토마토 - 이차원 배열 풀이 2차원 탐색을 3차원으로 확장한 문제. 3차원 배열로 초기화해서 풀 수 있지만 같은 팀원이 2차원 배열로 시도해서 도와 줬다. 2차원 배열로 풀기 위해서 배열을 [(높이)*(세로), (가로)] 로 초기화 한뒤 x좌표의 경계조건을 아래와 같이 설정해준다. 방향 벡터를 다음과 같이 정의할 때 새로 탐색할 좌표가 주어진 (세로) 범위에서 벗어나면 탐색을 생략한다.... BFS너비우선탐색BFS [백준 14502] 연구소 (JAVA) 시간 제한이 2초로 나름 널널한 편이다. N, M 모두 3~8로 최대 8X8=64개의 칸을 갖는다. 64개의 칸이 전부 0이라 해도 벽 3개를 세우는 경우의 수는 64C3 = 약 4만이기에 일일이 다 세워보는 브루트 포스 방식 적용. 벽을 세운 뒤에 바이러스를 퍼뜨리는 것은 BFS로 실행 makeWall(int cnt, int start) 벽 3개 세우기 (0인 부분에서 3개의 좌표 고르기 ... 알고리즘BFS브루트포스BFS [알고리즘/백준] 11725번 : 트리의 부모 찾기(python) pythonBFS알고리즘11725트리의 부모 찾기백준11725 [알고리즘/백준] 1743번 : 음식물 피하기(python) 간단한 bfs, dfs 문제이다 dfs bfs... pythonBFS알고리즘DFS1743백준음식물 피하기1743 [백준] 9466번* 사이클에 포함되어 있지 않은 원소의 개수 구하기 임의의 원소에서 시작해 사이클에 포함된 원소인지/아닌지 체크 -> 저장 💻 C++ 기반 ✔️ visited 배열에 bool값이 아닌 int값을 넣어주면 반복문을 돌 때마다 초기화를 안 해줘도 되므로 시간 복잡도가 O(N)이 된다.... 너비우선탐색BFS코딩테스트코테그래프Graph백준BFS [알고리즘/백준] 1389번 : 케빈 베이컨의 6단계 법칙(python) 1389pythonBFS알고리즘백준케빈 베이컨의 6단계 법칙1389 [Leetcode]994. Rotting Oranges You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-direction... leetcodepythonBFS코딩테스트breadth first searchBFS [백준]1941 소문난 칠공주(자바) 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과... 소문난 칠공주BFSboj브루트포스Java조합백준자바19411941 [JAVA] 백준 1726 로봇 길찾기 유형이라고 생각이 들어서 bfs로 풀어야겠다고 생각했습니다. 기존 길찾기에서 3칸까지는 비용이 같도록 처리하면 쉽게 풀수 있다고 생각했습니다. 1.메모리와 시간초과 부분이 가장 어려웠다 2.방향을 동서남북 0123 으로 처리했는데 동 <-> 서 남 <-> 북 180도 이동할때는 2를 주고 90도 이동할때는 1로 했는데 이부분 처리할때 생각할게 많아서 어려웠다.. 3. 처음에는 방문체크... 백준BFS알고리즘BFS 2260 회장뽑기 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다. 예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면... 플로이드와샬BFS알고리즘BFS [백준 1939 - Kotlin] 중량제한 BFSbinary_searchkotlinBFS [백준 9019] DSLR (JAVA) 처음엔 그리디 문제라 생각했다. 그러나 위와 같이 풀면, 다음과 같은 반례가 발생한다. A: 90 B: 9 인 경우 위의 로직으로 풀면 A와 B의 자리수가 다르기 때문에 A를 B와 자리수가 같아질 때까지 D 연산을 81번 하게 된다. 하지만 정답은 A를 L 연산 1번만 해주면 되기 때문에 잘못 된 로직이다. 그래서 결론은 내가 머리를 끙끙 앓지 말고, 그냥 D, L, S, R 가능한 모든 경... BFS알고리즘BFS [백준/python/1194]달이 차오른다,가자 문제 링크 : 문제의 스토리가 장황에서 처음 읽을 때는 이해되지 않았다. 자세히 읽어보니 미로문제였다. 다른 문제와 다른 점을 알파벳 키를 가질 수 있다는 것이다. 키를 판별해주는 과정이 너무 어려웠다. 그래서 다른 분의 블로그를 참고했다. 이 분은 이진법으로 표현했다. 1<<(ord("A")-65) 일 경우 1->1 1<<(ord("B")-65) 일 경우 2->10 1<<(ord("C")-... pythonBFS알고리즘어려운문제백준DequeBFS [백준 C++] 7576 토마토 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우... 7576baekjoonBFSC토마토중복허용7576 <BOJ>10026번: 적록색약 BFS 코드 틀을 알고 있으면 쉽게 풀 수 있는 전형적인 BFS 문제이다. 현재 좌표와 다음 좌표의 색상이 같으면 이동하는 방식으로 탐색한다. 2중 for문으로 방문하지 않은 좌표인지 파악해서 해당 좌표에서 BFS를 호출한다. 이 때 카운팅을 한다. → 각 색상별로 영역이 몇 개인지 파악함 적록색약인 경우를 위해 G영역을 R영역으로 바꾸고, visited를 초기화 한 뒤 다시 탐색한다.... pythonBFSboj너비우선탐색그래프탐색그래프백준BFS [programmers 84021] 퍼즐조각채우기 네이버 기출로도 알려진 퍼즐조각채우기를 풀어보았다 table의 블럭을 bfs로 탐색한다. (이 때 처음 좌표를 (0,0)으로 두고 그 다음 좌표는 상대적인 좌표를 저장한다) game_board의 빈칸도 bfs로 탐색한다(마찬가지로 상대적인 좌표) 이 때 bfs의 결과( (x,y) 좌표들)를 0이상의 값으로 바꿔 통일시켜 주었다 예를 들어, 예제 1을 보면 game_board의 ㅗ 모양과 ta... 프로그래머스BFS구현BFS [백준] 7576번 - 토마토 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프... 백준BFSBFS [C++] 백준 14502 : 연구소 메모리 제한 또는 시간 제한이 걸릴까봐 걱정되었는데 512MB, 2초정도면 모든 임시값을 copy해도 괜찮을 정도라는 것을 알게 되었다. 벽 3개 세우기는 백트래킹(DFS)를 이용한다. 순열을 구하는 것과 같다. 모든 경우의 수에서 3개씩 뽑아 줄세우면 된다. STL 라이브러리의 algorithm을 사용하면 copy를 한 줄에 끝낼 수 있다. copy(copy할 것의 첫 주소, copy할 것... 백트래킹2022.03BFS알고리즘DFS삼성cpp백준2022.03 [백준 C++] 2573 빙산 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 그림 1. 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 따라서 그림 1의 빙산은 일년후에 그림 2와 ... baekjoonBFS2573C빙산2573 [백준 C++] 2636 치즈 아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. <그림 1>의 경우, 치즈의 구멍을 둘... 치즈2636baekjoonBFSC2636 백준 2589 : 보물섬 1. 접근 결국 가장 먼 두 지점을 구하는 문제이고, "가장" 긴 거리를 구하는 문제에는 BFS가 가장 적절하다. (한번에 한단계씩 이동하기때문에 가장 길거나, 가장 짧은 거리를 구할 때에는 BFS가 더 적절하다) 초기 지도를 입력받고, 그 지도의 값을 BFS로 1씩 더해주면서 가장 큰 값을 택하면 된다. 전체 변수 값이 작기 때문에 모든 L 값에 대해 BFS를 구해주었다. 입장할때마다 초기... BFScppBFS 알고리즘 스터디 11주차[dfs/bfs]_02 문제 : 점프 점프 문제 설명 : 배열의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 문제. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다. 코드 : 문제 풀이: 밑에 사진처럼 처음 dp[0]을 0으로 설정하고, arr배열의 해당 데이터의 크기만큼 dp[]의 값들을 1씩 더해가면서 구한다. 참조 :... DFS백준11060BFS알고리즘스터디BFS [백준] 7569번 - 토마토 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프... 백준BFSBFS [C++] 백준 7576 : 토마토 의 업그레이드 버전 문제 상하좌우위아래 를 확인하기 위해서는 위로 갈 경우, 아래로 갈 경우, 좌로 갈 경우, 우로 갈 경우... 해서 6가지의 경우 수만 확인하면 된다. 이걸 조심하자. 처음에는 모든 경우의 수를 내가 배열에 넣어서 구하려고 했는데 굉장히 불필요한 일이었다. cnt를 세기 위해 바로 map으로 표시했기에 visit 여부는 표시할 필요가 없다. 때문에 7576 번에서 푼 것과... 2022.03BFS알고리즘cpp백준2022.03 [백준] 1697 - 숨바꼭질 (Python) 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 그래프 탐색 너비 우선 탐색(bfs) 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. 수빈이가 5 → 10 ... BFSboj알고리즘BFS 이전 기사 보기
[백준] 2554 : 미로만들기 BFS와 heap을 사용해서 계속 내가 동서남북으로 이동할 수 있는 좌표 중 최소 비용(벽을 뚫는 횟수)을 가지는 좌표로만 이동하게 하는 것이 핵심! 그때 이미 while heap: 안에서 계속 최소 비용을 가지는 좌표로만 이동해주고 있으므로, visited했던 곳을 또 방문할 필요가 없어진다. visited 방문 기록을 남겨주는 이유가 바로 그것! 방문했던 곳을 방문하지 않게 하려고!! 풀... 다시풀문제그래프다익스트라BFS백준코딩테스트BFS 백준 2623 음악프로그램 위상정렬 문제다! 가수들을 그래프의 노드로 생각하고, 입력으로 주어지는 출연 가수의 순서를 단방향성 간선으로 연결해주면 싸이클이 없는 단방향성 그래프가 완성된다 예제 입력의 경우 이렇게 graph와 in_degree가 완성되고 여기서 in_degree는 index의 노드가 몇개의 노드들에게 연결 당했는지(?) 를 나타낸다 in_degree가 0인 노드들을 queue에 삽입하면서 bfs를 통해... algorithmbojTopological SortpythonBFSGraphBFS 백준 16946 벽 부수고 이동하기 4 dfs,bfs를 사용한 풀이 가장 처음 접근은 dfs를 사용했습니다 현재 좌표값이 1일 경우 dfs를 통해서 연결되어 있는 0값들을 카운팅해서 board[i][j]를 수정했습니다 정답은 맞았는데 시간초과가 떴구요 구글에 검색해서 풀이법을 찾아봤습니다 시간을 단축하기 위해 0이 연속적으로 있는 구역들을 그룹핑해서 저장 후 카운팅 bfs를 통해 0의 범위들에게 그룹번호를 지정해줍니다 예를 들어 ... algorithmbojpythonBFSGraphBFS 프로그래머스 카드 짝 맞추기 python cpp 풀이법은 bfs와 dfs를 사용해서 모든 경우의 수를 다 탐색하는 것입니다. 예를 들어서 블록의 종류가 3개라면 이렇게 모든 경우를 다 탐색하는데 이 때 블록의 한쌍이 2개이기 때문에 1번째 블록을 먼저 지우고 2번째 블록을 지우는 경우와 2번째 블록을 지우고 1번째 블록을 지우는 경우까지 전부 생각해서 구현해주면 됩니다 그리고 블록간의 거리는 문제에서 주어진 조건으로 b... DFSalgorithm카카오 기출programmerscpppythonBFSGraphsimulationBFS 백준 [7569] 토마토 - 이차원 배열 풀이 2차원 탐색을 3차원으로 확장한 문제. 3차원 배열로 초기화해서 풀 수 있지만 같은 팀원이 2차원 배열로 시도해서 도와 줬다. 2차원 배열로 풀기 위해서 배열을 [(높이)*(세로), (가로)] 로 초기화 한뒤 x좌표의 경계조건을 아래와 같이 설정해준다. 방향 벡터를 다음과 같이 정의할 때 새로 탐색할 좌표가 주어진 (세로) 범위에서 벗어나면 탐색을 생략한다.... BFS너비우선탐색BFS [백준 14502] 연구소 (JAVA) 시간 제한이 2초로 나름 널널한 편이다. N, M 모두 3~8로 최대 8X8=64개의 칸을 갖는다. 64개의 칸이 전부 0이라 해도 벽 3개를 세우는 경우의 수는 64C3 = 약 4만이기에 일일이 다 세워보는 브루트 포스 방식 적용. 벽을 세운 뒤에 바이러스를 퍼뜨리는 것은 BFS로 실행 makeWall(int cnt, int start) 벽 3개 세우기 (0인 부분에서 3개의 좌표 고르기 ... 알고리즘BFS브루트포스BFS [알고리즘/백준] 11725번 : 트리의 부모 찾기(python) pythonBFS알고리즘11725트리의 부모 찾기백준11725 [알고리즘/백준] 1743번 : 음식물 피하기(python) 간단한 bfs, dfs 문제이다 dfs bfs... pythonBFS알고리즘DFS1743백준음식물 피하기1743 [백준] 9466번* 사이클에 포함되어 있지 않은 원소의 개수 구하기 임의의 원소에서 시작해 사이클에 포함된 원소인지/아닌지 체크 -> 저장 💻 C++ 기반 ✔️ visited 배열에 bool값이 아닌 int값을 넣어주면 반복문을 돌 때마다 초기화를 안 해줘도 되므로 시간 복잡도가 O(N)이 된다.... 너비우선탐색BFS코딩테스트코테그래프Graph백준BFS [알고리즘/백준] 1389번 : 케빈 베이컨의 6단계 법칙(python) 1389pythonBFS알고리즘백준케빈 베이컨의 6단계 법칙1389 [Leetcode]994. Rotting Oranges You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-direction... leetcodepythonBFS코딩테스트breadth first searchBFS [백준]1941 소문난 칠공주(자바) 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과... 소문난 칠공주BFSboj브루트포스Java조합백준자바19411941 [JAVA] 백준 1726 로봇 길찾기 유형이라고 생각이 들어서 bfs로 풀어야겠다고 생각했습니다. 기존 길찾기에서 3칸까지는 비용이 같도록 처리하면 쉽게 풀수 있다고 생각했습니다. 1.메모리와 시간초과 부분이 가장 어려웠다 2.방향을 동서남북 0123 으로 처리했는데 동 <-> 서 남 <-> 북 180도 이동할때는 2를 주고 90도 이동할때는 1로 했는데 이부분 처리할때 생각할게 많아서 어려웠다.. 3. 처음에는 방문체크... 백준BFS알고리즘BFS 2260 회장뽑기 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다. 예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면... 플로이드와샬BFS알고리즘BFS [백준 1939 - Kotlin] 중량제한 BFSbinary_searchkotlinBFS [백준 9019] DSLR (JAVA) 처음엔 그리디 문제라 생각했다. 그러나 위와 같이 풀면, 다음과 같은 반례가 발생한다. A: 90 B: 9 인 경우 위의 로직으로 풀면 A와 B의 자리수가 다르기 때문에 A를 B와 자리수가 같아질 때까지 D 연산을 81번 하게 된다. 하지만 정답은 A를 L 연산 1번만 해주면 되기 때문에 잘못 된 로직이다. 그래서 결론은 내가 머리를 끙끙 앓지 말고, 그냥 D, L, S, R 가능한 모든 경... BFS알고리즘BFS [백준/python/1194]달이 차오른다,가자 문제 링크 : 문제의 스토리가 장황에서 처음 읽을 때는 이해되지 않았다. 자세히 읽어보니 미로문제였다. 다른 문제와 다른 점을 알파벳 키를 가질 수 있다는 것이다. 키를 판별해주는 과정이 너무 어려웠다. 그래서 다른 분의 블로그를 참고했다. 이 분은 이진법으로 표현했다. 1<<(ord("A")-65) 일 경우 1->1 1<<(ord("B")-65) 일 경우 2->10 1<<(ord("C")-... pythonBFS알고리즘어려운문제백준DequeBFS [백준 C++] 7576 토마토 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우... 7576baekjoonBFSC토마토중복허용7576 <BOJ>10026번: 적록색약 BFS 코드 틀을 알고 있으면 쉽게 풀 수 있는 전형적인 BFS 문제이다. 현재 좌표와 다음 좌표의 색상이 같으면 이동하는 방식으로 탐색한다. 2중 for문으로 방문하지 않은 좌표인지 파악해서 해당 좌표에서 BFS를 호출한다. 이 때 카운팅을 한다. → 각 색상별로 영역이 몇 개인지 파악함 적록색약인 경우를 위해 G영역을 R영역으로 바꾸고, visited를 초기화 한 뒤 다시 탐색한다.... pythonBFSboj너비우선탐색그래프탐색그래프백준BFS [programmers 84021] 퍼즐조각채우기 네이버 기출로도 알려진 퍼즐조각채우기를 풀어보았다 table의 블럭을 bfs로 탐색한다. (이 때 처음 좌표를 (0,0)으로 두고 그 다음 좌표는 상대적인 좌표를 저장한다) game_board의 빈칸도 bfs로 탐색한다(마찬가지로 상대적인 좌표) 이 때 bfs의 결과( (x,y) 좌표들)를 0이상의 값으로 바꿔 통일시켜 주었다 예를 들어, 예제 1을 보면 game_board의 ㅗ 모양과 ta... 프로그래머스BFS구현BFS [백준] 7576번 - 토마토 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프... 백준BFSBFS [C++] 백준 14502 : 연구소 메모리 제한 또는 시간 제한이 걸릴까봐 걱정되었는데 512MB, 2초정도면 모든 임시값을 copy해도 괜찮을 정도라는 것을 알게 되었다. 벽 3개 세우기는 백트래킹(DFS)를 이용한다. 순열을 구하는 것과 같다. 모든 경우의 수에서 3개씩 뽑아 줄세우면 된다. STL 라이브러리의 algorithm을 사용하면 copy를 한 줄에 끝낼 수 있다. copy(copy할 것의 첫 주소, copy할 것... 백트래킹2022.03BFS알고리즘DFS삼성cpp백준2022.03 [백준 C++] 2573 빙산 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 그림 1. 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 따라서 그림 1의 빙산은 일년후에 그림 2와 ... baekjoonBFS2573C빙산2573 [백준 C++] 2636 치즈 아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. <그림 1>의 경우, 치즈의 구멍을 둘... 치즈2636baekjoonBFSC2636 백준 2589 : 보물섬 1. 접근 결국 가장 먼 두 지점을 구하는 문제이고, "가장" 긴 거리를 구하는 문제에는 BFS가 가장 적절하다. (한번에 한단계씩 이동하기때문에 가장 길거나, 가장 짧은 거리를 구할 때에는 BFS가 더 적절하다) 초기 지도를 입력받고, 그 지도의 값을 BFS로 1씩 더해주면서 가장 큰 값을 택하면 된다. 전체 변수 값이 작기 때문에 모든 L 값에 대해 BFS를 구해주었다. 입장할때마다 초기... BFScppBFS 알고리즘 스터디 11주차[dfs/bfs]_02 문제 : 점프 점프 문제 설명 : 배열의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 문제. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다. 코드 : 문제 풀이: 밑에 사진처럼 처음 dp[0]을 0으로 설정하고, arr배열의 해당 데이터의 크기만큼 dp[]의 값들을 1씩 더해가면서 구한다. 참조 :... DFS백준11060BFS알고리즘스터디BFS [백준] 7569번 - 토마토 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프... 백준BFSBFS [C++] 백준 7576 : 토마토 의 업그레이드 버전 문제 상하좌우위아래 를 확인하기 위해서는 위로 갈 경우, 아래로 갈 경우, 좌로 갈 경우, 우로 갈 경우... 해서 6가지의 경우 수만 확인하면 된다. 이걸 조심하자. 처음에는 모든 경우의 수를 내가 배열에 넣어서 구하려고 했는데 굉장히 불필요한 일이었다. cnt를 세기 위해 바로 map으로 표시했기에 visit 여부는 표시할 필요가 없다. 때문에 7576 번에서 푼 것과... 2022.03BFS알고리즘cpp백준2022.03 [백준] 1697 - 숨바꼭질 (Python) 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 그래프 탐색 너비 우선 탐색(bfs) 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. 수빈이가 5 → 10 ... BFSboj알고리즘BFS 이전 기사 보기