BFS

[python3] 백준 1039 (교환, BFS)

N값으로 값이 주어지는 경우 i 번째와 j 번째를 바꾸어 새로운 수를 만든다. 이때 K번 연산을 하여 나올 수 있는 최댓값을 구하면 된다. N값은 1,000,000으로 값이 커보이지만 문자열 연산을 하기 때문에 긴 값은 아니다. K값 또한 10으로 시간 복잡도상으로 큰 값이 아니다. 만약 2133이 존재할때 i=0, j=2로 하는 경우 3123이 된다. i=0,j=3로 하는 경우 3132이 된다. 그렇다면 2133을 1번 변환하여 만들수 있는 최댓값은 3132이다. 그러나 2133을 2번 변환하여 만들수 있는 값이 3321인데 3132로는 3321을 만들수 없다. 즉 K-1번의 결과값이 K번의 결과 값과는 상관이 없다. 따라서 모든 경우의 수를 탐색해야 K번 연산 했을때의 최댓값을 구할 수 있다. 그렇다..

[python3] 백준 1194 풀이 ( "달이 차오른다, 가자." , BFS )

이번 문제는 오랜만에 그래프이다. 우선 문제를 읽어보면 몇가지 포인트가 존재한다. 1. 이동 횟수의 최솟값을 구한다. => BFS로 푼다. 2. 키가 있어야 문을 열수 있다. => 키를 찾고 왔던길을 다시 갈 수 있다. => visited를 키에 따라 따로 관리해야 한다. => 그럼 키에 따른 visited를 관리해야한다. 따라서 3차원으로 visited를 관리해야 한다. * 이때 키는 bitmasking으로 관리해야 배열에 넣고 관리가 가능하다. 3차원으로 visited를 관리해야 하는 경우에는 [y][x][key]로 관리하여 key일때 y,x가 true 상태인지 false 상태인지 저장해준다. 사실 이러한 방식이 처음이라 이해가 어려웠다. 만약 key가 3이고(000000000011 => a,b키를 ..

[python3] 백준 14360 풀이 ( 구슬 탈출 2, BFS, 방문체크 없음 )

이번 문제는 저번 주 스터디에서 풀지 못한 문제였는데, 생각할 시간이 상당히 많았기 때문에 겨우 풀었다. 우선 문제를 살펴보자 문제를 요약하면 상하좌우로 움직일 수 있는 판을 가지고 있을 때, 빨간공만을 출구로 뽑아내는 경우 얼마나 시간이 걸리는지 알아내는 문제이다. 이때 한 방향으로 움직이는 경우 두 공이 못 움직일 때까지 움직인다. 우선 우리는 최소로 움직여서 공을 뽑아낼 것이다. 즉, 최단 거리나 최단 경우의 수를 구할 때는 역시 BFS를 사용해야한다. 두번째로 우리는 2공(빨강,파랑)을 상하좌우로 움직일 것이다. 움직일 때는 한번에 움직이지 못하고 한 칸씩 이동하면서 움직여야한다. 왜냐하면 그래야 겹치는 경우를 피할 수 있다. 그런데 겹치는 경우를 위해 한 칸씩 움직인다고 한다면 방향에 따라 두 ..

[python3] 백준 16236 풀이 ( 아기상어, 그래프, BFS, sort, pq? )

이번 문제도 역시나 좀 헤맸다. 이번 문제는 BFS로 쉽게 풀릴 줄 알고 살짝 깝쳐 봤으나 역시나 생각치 못한 케이스가 존재해서 결국 다시 코딩한 문제이다. 문제를 쓰악 읽어보자. 우선 문제는 아기상어의 성장에 관한 이야기다. 스토리처럼 느껴져서 문제 읽는 동안 재밌었다. 여튼 문제에서 나오는건 아기 상어가 성장하기 위해서 물고기를 먹어야한다. 그런데 먹이를 먹는데 여러 조건이 존재한다. 조건 1. 먹을 수 있어야함. (자기보다 크기가 작아야함.) 2. 거리가 가까워야 함. 3. 위 물고기 선호 4. 왼쪽 물고기 선호 1번 조건과 2번 조건은 BFS로 최단 경로를 찾으며 먹을 수 있는 물고기를 찾으면 된다. 3번 조건과 4번 조건은 같은 거리에 존재하는 물고기들의 좌표를 비교하여 조건에 맞는 물고기부터 ..

백준 3055 C++ 풀이 (탈출, BFS)

이번에는 c++로 BFS문제를 풀어보자. 사실 엄청 어렵지는 않은 문제였다. 알고리즘을 어떻게 사용해서 풀지 쉽게 이해할 수 있었다. 그러나 문제는 c++!!!!! 맨날 파이썬으로 풀다가 c++을 접했더니 아주 신경써야할 게 한 두개가 아니다. 괜히 알고리즘 고수들의 언어가 아니었다. 준나 어렵다. 문제는 간단하다. 귀여운 고슴도치가 비버굴로 피난을 가는데 걸리는 시간을 구한다. 단, 물이 넘치게 되는 조건이 있는데 시간이 갈수록 물이 주변 지역으로 퍼진다. 이를 피하며 굴로 이동하면 된다. 가장 빠른 길을 찾는 것이기 때문에 BFS를 선택하면 된다. 또한 고슴도치는 물이 넘치는 지역으로 이동하면 안되기 때문에 물을 먼저 이동시키고 고슴도치를 이동시키면 된다. 1. 땅굴의 위치, 물의 위치, 고슴도치의 ..

백준 2206 파이썬 풀이 (BFS, 벽 부수고 이동하기, 이차 배열 사용)

이 문제는 정말 나를 못살게 괴롭히는 놈이었다. 배열을 어떻게 해야할지 어떤 기준으로 visited를 하게 할지 굉장히 고민을 많이 하게 만들었다. 3차원 배열로 풀으라는데 내 방식대로 풀기 위해 상당히 고생을 했다. 우선 경우를 나누어본다. 벽을 뿌수고 이동하는 경우에는 다양하게 길이 갈리게 된다. 따라서 이미 누군가 지나간 길에 대해서 계속 갈지 말지를 정해야한다. 편의상 플레이어(경로를 가는 포인트)와 스킬(벽을 부쉈는지 아닌지)이라고 하겠다. 그렇다면 4가지 경우로 나눈다. 1. 스킬을 쓰지 않은 플레이어가 지나간 자리를 스킬을 쓰지 않은 플레이어가 마주쳤을때 => 더이상 진행할 이유가 없다. 왜냐면 앞선 플레이어가 더 효율적 2. 스킬을 쓰지 않은 플레이어가 지나간 자리를 스킬을 쓴 플레이어가 ..

백준 1707 python 풀이 (이분 그래프, BFS)

일단 처음에 문제를 읽고는 생각보다 쉽다고 느꼈다. 단순히 BFS로 탐색하면서 이전 값이랑 비교하면 되겠구만 했다. 그런데 구현하는데 상당히 애를 먹었고, 시간초과가 떠서 오랜 삽질 중이다. 우선 시간초과 코드는 아래와 같다. from collections import deque import sys input = sys.stdin.readline T = int(input()) def BFS(v,e,color, d,q): color[q[0]] = 1 visited = [0 for i in range(v+1)] while q: target = q.popleft() visited[target] = 1 targets = d[target] for t in targets: if visited[t] == 0: q.a..

백준 7562 python 풀이 (나이트의 이동, BFS, 그래프)

문제는 나이트가 위와 같이 움직일 수 있을때 몇번 움직이면 원하는 목적지에 도달하는지 구하는 문제이다. 이전에 BFS문제와 아주 유사하다. 다만 그전에는 한칸씩 상하좌우로 움직였지만 이번에는 좀더 여러방면으로 움직이는 차이가 있다. 이때 가장 적은 움직임의 수를 구해야 하기 때문에 DFS가 아닌 BFS로 풀면 된다. 1. BFS를 구현 2. 좌표의 움직임을 구현 3. 이미 움직이거나 움직일 곳은 표시하여 중복을 제거 이를 토대로 코드를 구현하면 아래와 같다. from collections import deque T = int(input()) def BFS(l, start, end): M = [[0 for i in range(l)] for i in range(l)] M[start[0]][start[1]] ..