본문 바로가기

너비우선

 (11)
[C++/PGS] Lv.2 : 게임 맵 최단거리 (BFS) 깊이/너비 우선 탐색(DFS/BFS) : 게임 맵 최단거리 문제 출처 - 프로그래머스 코딩테스트 고득점 Kit 문제 설명 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 ..
[C++/BOJ] 14940 : 쉬운 최단거리 (BFS) / test case 문제 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라. 문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자. 입력 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다. 출력 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 백준 실버 1. 예전에는 골5였던 듯 하다 하 진짜 혼자 끙끙대면서 한시간동안 열심히 풀었다 맞추고 나서 다시 코드를 보니 ..
[코드트리] DFS / BFS 소마 서류에 덜컥 붙어버리고, 코테 준비 4일전사 도전... 자주 나온다는 유형을 급하게 공부해봅니다 하하 DFS는 Depth First Search, 깊이 우선 탐색입니다. 이름처럼 최대한 깊게 탐색한 후 더 이상 도달할 수 없는 상황이라면 다시 이전으로 돌아갑니다. 중요한 것은 깊게 탐색하고 나서 이전과정으로 돌아가야 한다는 점 입니다. DFS는 재귀(스택)를 활용해 구현하는 경우가 많습니다. 즉, 방문할 수 있는 지점이 있다면 그 지점을 방문하는 함수를 재귀적으로 호출하고, 더 이상 방문할 곳이 없다면 함수를 종료하면 될 것입니다. 다만, 이미 방문했던 지점을 또 방문하면 효율이 떨어지기 때문에 이전에 방문했던 지점은 다시 방문하지 않아야 합니다. 한 번 방문한 지점은 어떤 처리를 해서 더 이상 방..
728x90

티스토리툴바