BFS

문제 링크 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 이번 문제는 이전 벽 부수고 이동하기 시리즈 1~3과는 조금 다릅니다. 이전 문제들은 벽을 부수고 지나가면서 최단 경로를 구하는 문제였지만, 이번 4번째 문제는 벽을 부수고 이동할 수 있는 칸의 개수를 세어보는 경우의 수 문제로 바뀌었습니다. 이번 문제는 풀면서 저도 우여곡절이 살짝 있었기에, 그런 우여곡절들을 공유하면서 풀이해보겠습니다. 풀이 DFS로 풀이했습니다. (BFS도 가능) 보통 경우의 수는 백트래킹으로 풀이하는데, 백트..

문제 링크 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 링크 : 벽 부수고 이동하기 1 링크 : 벽 부수고 이동하기 2 벽 부수고 이동하기 1과 2에 이어서 3번 문제입니다! 이번 문제도 저번 문제들의 연장선에 있습니다. 저번 문제에서 낮과 밤이 추가됐죠! 이번 문제도 한번 풀어보겠습니다~ 풀이 이전 문제와 마찬가지로 4중배열 VST + BFS로 풀이하면 됩니다. 이전 문제의 DP는 \(k\)(벽을 부술 수 있는 한도)와 \(n, m\)(맵의 행렬 길이)로 풀 수 있었습니..

문제 링크 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 저번에 작성했던 벽 부수고 지나가기 첫 문제 포스팅에 이어 두번째 문제입니다. 이번 문제는 첫번째 문제에서 조건 하나만 변경한 문제이니, 그렇게 차이는 나지 않습니다! 풀이해보겠습니다~ 풀이 이전 문제와 마찬가지로 VST(3중배열) + BFS로 풀이하면 됩니다. 대신 이전 문제는 2개까지만 벽을 부수는 것을 허용했지만, 이번 문제는 10개까지 벽을 부술 수 있습니다. 따라서 그만큼 VST배열의 크기를 늘려서 저장하고,..

문제 링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 요새 프로젝트를 진행한다고 블로그 글을 잘 못쓰네요 😂 그래서 오늘부터 간단하게 벽 부수고 이동하기 문제 시리즈를 진행할 계획입니다. 시리즈는 1부터 4까지 있고, 이번 포스팅부터 시작합니다! 풀이 VST (3중배열) + BFS로 풀이하면 됩니다. 이 문제는 흔하게 볼 수 있는 BFS를 이용한 최단 거리 문제의 응용 버전이라고 볼 수 있겠습니다. 보통 최단 거리 문제는 `visit` 배열로 전에 갔던 경로를 체크하여 가지 않는..

문제 링크 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net BFS 응용 문제 중 하나입니다. 처음에 '상범이가 어떻게 이동하지?' 라는 생각으로 시간이 좀 걸렸습니다. 백트래킹, 최단거리 등을 생각하면서 고민했는데, 결국엔 BFS로 다 해결할 수 있었습니다. 풀이 불과 상범이의 queue를 각각 만들어서 서로의 거리를 비교하면 됩니다. 불의 Queue와 Vst(방문배열), 상범이의 Queue와 Vst(방문배열)을 각각 만들어서 큐에 넣어줍니다. 불은 간단하게 BFS로 상하좌우로 퍼지게 하면서, 방문배열에 거리를 적어둡니다..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 서론 상하좌우로 가긴 하는데, 맨 끝까지 간다는 것만 빼면 흔한 BFS 문제입니다. 뻘짓을 제외하면 늘 BFS를 풀던대로 풀었습니다. 풀이 들어온 입력(board)을 재처리 해줍니다. 입력에서 'G'를 '.' 으로 재처리해주고, 따로 저장해줍니다. 그리고 'R'은 Queue에 넣어줍니다(시작지점이기 때문에 재처리 불필요) BFS를 돌려줍니다. 그리고 vst 배열에 이동거리를 저장해줍니다. 다음으로 갈 지점(nx, ny)을 정할 때는 반복문으로 1씩 더해줬습니다. 보드의 크기가 100 이하이기 때문에..