본문 바로가기
728x90
728x90

BFS

[Python][백준 2234][BFS] 성곽 - 컴도리돌이 풀이 과정 본 문제는 전형적인 BFS문제이다. 왜냐하면 연결되어 있는 방의 개수를 물어봤기 때문이다. 부가적으로 특이한 요소를 첨가하였다. 각 좌표들 간에 연결되었는지를 15 이하의 값으로 주어져있다. 0~15 (?) 문제에서 언급한 힌트대로 이 문제는 좌표 이동을 비트 마스킹을 해준다. 하지만 비트 마스킹이 익숙하지 않아서,,, 나는 문자열로 표시를 하였다. 물론 하는 방법은 비트 마스킹이랑 똑같다..! "0000" ~ "1111" 맨 왼쪽부터 서북 동남을 의미하고 1은 이동 불가(벽으로 연결)를 의미하고 0은 이동 가능을 의미한다. 1. m*n 만큼 반복문을 돌려서 해당 (i, j) 위치를 방문하지 않을 경우 BFS 탐색을 한다. 2. 현재 위치 값을 bin함수를 이용하여 이진수를 나타내고 크기를 4.. 더보기
[Python][백준 1194][BFS][bit masking] 달이 차오른다, 가자. - 컴도리돌이 풀이과정 해당 문제는 방문 표시만 제대로 하면 쉽게 해결할 수 있는 문제이다. 물론 방문 표시가 생각보다 까다롭다. 😂 시작점에서 끝점까지 도달하는 최단 거리는 너비 우선 탐색(BFS)으로 구현하면 된다. 그렇다면 이 문제의 핵심은 방문 표시이다. 탈출을 하기 위해서는 '.' 공간만 이용할 수 있다. 물론 주어진 n*m 행렬 맵에서는 키라는 특이한 요소를 첨가했다. 키의 종류는 a, b, c, d, e, f 총 6가지이며, 키의 종류 따른 문의 종류도 A, B, C, D, E, F 총 6가지이다. 문제에서는 탈출구까지 가는 길에 문이 있으면 해당 문에 맞는 키 값을 소유하고 있어야 한다. 그렇기 때문에 BFS 탐색할 때 방문 표시를 가지고 있는 키 값들에 따라 해주어야 한다. 키의 종류는 총 6가지이다... 더보기
[Python][백준 23085][BFS] 판치기 - 컴도리돌이 t or reversed_front > h : continue if t - reversed_back + reversed_front in visited : continue visited[t-reversed_back+reversed_front] = True q.append([t-reversed_back+reversed_front,depth+1]) else : print(-1) 더보기
[Python][백준 17836][BFS] 공주님을 구해라! - 컴도리돌이 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 과정 1. bfs로 해결을 하였다. q에는 x, y 좌표 값과 이동 시간, 무기를 갖고 있는지 확인용 key 값을 1x4 배열로 넣어줬다. 2. 주의할 점은 방문 표시를 n x m 행렬로 해주면 안 된다. n x m으로 방문 표시를 하면 용사가 무기를 가질 때, 용사가 무기가 없어서 우회했던 경로를 다시 방문할 수 없기 때문에 시간 초과가 발생할 것이다. 3. q에서 pop을 할 때 x, y 값이 공주가 있는 곳(n-1, m-1)으로 올 경우.. 더보기
[파이썬][백준 13460][BFS] 구슬 탈출 2 - 컴도리돌이 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 방법 1. 일단 알고리즘은 BFS를 사용하였다. 2. 큐에는 빨간색 공의 좌표(rx, ry)와 파란색의 공의 좌표(bx, by) 그리고 이동 횟수를 포함하고 있다. 3. 이동 횟수가 10이 넘어가면 break 시키고 -1 값을 반환해주었다. 4. 방문 표시는 빨간색의 공과 파란색의 공을 str으로 변환해주어서 dict에 True로 삽입하여 방문 표시를 체크하였다. 5. 상하좌우 4개의 방향으로 move 함수를.. 더보기
[c++][백준 21937][bfs] 작업 - 컴도리돌이 21937번: 작업 민상이가 작업할 개수 $N$와 작업 순서 정보의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째줄부터 $M + 1$ 줄까지 작업 $A_i$와 작업 $B_i$가 공백으로 구분되어 주어진다. 이때 두 값의 의미는 작 www.acmicpc.net 풀이 과정 해당 문제는 bfs,dfs로 풀어도 될 것같다. 나는 bfs가 친숙해서 해당 문제를 bfs를 풀었다. 입력 값 'process'라는 벡터는 이차원 배열로 구성하였고 해당 노드의 자식 노드를 삽입해줬다. 그 다음 문제에서 요구하는 x라는 입력 값을 받아서 해당 x에 대한 bfs 탐색을 한다. 그 다음부터는 평범한 bfs 코드이다. x 밑에 있는 자식 노드가 있고 해당 자식 노드를 방문하지 않았다면 큐에 삽입하여 해당 자식노드를 탐색.... 더보기
[c++][백준 21938][bfs] 영상 처리 - 컴도리돌이 21938번: 영상처리 화면의 세로 $N$, 가로 $M$ 값이 공백으로 구분되어 주어진다. 두 번째 줄부터 $N + 1$줄까지 $i$번째 가로를 구성하고 있는 픽셀의 $R_{i,j}$, $G_{i,j}$, $B_{i,j}$의 값이 공백으로 구분되어 총 $M$개 주어진 www.acmicpc.net 풀이 과정 해당 문제는 bfs로 문제를 해결할려고 결정하였고, 정말 쉽게 풀었다. 하지만 결과는 실패.. 정말 맞왜틀.. 처음에는 내 로직이 틀린 줄 알았다. 그래서 다른 사람 코드를 보고 참고했는데 좀 더 간단하게 구현했을 뿐이지 별 차이가 없는 정말 쉬운 문제였는데,,, 그래서 반환 값 문제인가 해서 long long으로도 바꿔보고 double형으로도 바꿔봤지만 계속 실패만 하였다. 그래서 차근차근 input.. 더보기
[c++][백준 2146][BFS] 다리 만들기 - 컴도리돌이 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net * 풀이 과정 1. 육지와 육지 사이의 구분이 필요하기 때문에 육지마다 번호를 표시하였다.(처음 육지를 1로 입력받는 것을 -1로 입력받았다.) 2. 육지와 육지 사이의 다리를 놓는다. 1) 번호에 따른 육지의 x, y 값들을 queue에 넣고 방문 표시를 한다. 2) 다른 육지 번호가 나오면 다리의 값을 return 한다. 3) 바다가 나오면 queue에 넣고 다리가 설치했다고 가정을 하고 bridge 값도 +1을 시켜서 queue에 넣는다. 해당 좌표는 방문 표시.. 더보기

티스토리툴바