본문 바로가기

반응형

BFS

(12)
[BOJ] 14923. 미로탈출 미로 탈출클릭시 이동합니다. 어떻게 풀까? BFS 문제입니다!해당 캐릭터의 이동 시간은 1이기 때문에, BFS에서 해당 도착점에 도착했을 때가 처음으로 나오는 시간이 바로 해당 지점에 도착할 수 있는 최소 시간입니다! 그리고, 만약 캐릭터가 이동하고자 하는 방향이 이전에 한 번 이동했던 방향이라면 다시 방문할 필요가 없죠.그 말은 가고자 하는 방향을 한번 돌아서 간다는 것이기 때문입니다! 최소 시간과는 거리가 멀어지죠. 따라서, 해당 맵에 들어갔던 최소 시간을 check[y][x]에 표시합시다! 다만, 이 문제는 탈출을 하는데 조건이 하나가 더 있습니다!바로, 마법을 쓸 수 있다는 것이지요.이 마법의 유무가 최소를 만들 수 있는 또 다른 변수가 될 수 있습니다. 왜냐하면, 조금 늦게 왔더라도, 마법이 있..
[BOJ] 14226. 이모티콘 이모티콘클릭시 이동합니다. 어떻게 풀까? 우선, 한 상태에서 달라질 수 있는 것들은 총 3개 이죠. 1. 현재 화면에 있는 이모티콘 수2. 클립보드에 저장된 이모티콘의 수3. 시간 특히, 시간 같은 경우는 모든 연산에서 1초로 동일합니다.따라서, bfs를 이용해서 딱 현재 화면에 있는 이모티콘의 수가 처음으로 나온다면, 그것이 바로 해당 화면에 이모티콘을 만들 수 있는 최소의 시간인 것이죠. 그럼, 만약 큐에서 상태를 뽑았는데, 이미 이전에 화면에 있는 이모티콘의 수와 클립보드에 저장된 이모티콘의 수가 같은 상태를 봤었다면 어떨까요?? 어짜피 똑같은 처리를 다시 한 뒤에 똑같은 상태가 큐에 저장되기 때문에 다시 볼 필요가 없습니다!! 따라서, 이전에 처리한 상태를 저장하기 위해서 visit은 [화면에 있..
[BOJ] 13901. 로봇 로봇클릭시 이동합니다. 어떻게 풀까? 우선, 처음에 방향이 4개가 주어집니다.그리고 4개의 방향에서 나아가지 못하면, 현재의 위치를 출력해야하죠! 따라서, 저는 4개의 방향을 살펴보면서 4개의 방향으로 가지 못하면 cont라는 bool 변수를 false로 만들어서 while문을 빠져나오게 했습니다!한 번이라도 움직이면, 해당 방향으로 움직이기 때문에 계속 루프를 돌겠죠.그리고, 움직인 방향에는 벽을 설치해서 다시 돌아올수 없게 했습니다. 또 중요하게 생각해볼 점은 1. '만약 움직이면 계속 같은 방향으로 움직인다.' 라는 점과2. '만약, 사용자가 지정한 다음 방향이 없다면 맨 처음 방향으로 돌아간다.' 라는 점이겠죠. 1번 같은 경우는, 자신의 현재 방향을 변수로 가지고 있으면 쉽게 해결됩니다!2번의 ..
[SW Expert Academy] 길찾기 길찾기 SW Expert Academy는 문제 복제가 금지되어 있기 때문에 링크로 대체하겠습니다. 어떻게 풀까? 대표적인 DFS / BFS 문제입니다.저 같은 경우는 그냥 시작점에서 큐를 돌려서 BFS를 이용해서 풀었습니다! 0번 노드에서 시작해서 0번 노드에서 이어지는 노드들을 모두 큐에 넣은 후에 방문 했다는 것을 체크해 둡니다.만약, 99번 노드가 나온다면 바로 연결되어있다는 것으로 끝내주면 됩니다.하지만 큐가 빌 때까지 99번 노드를 찾을 수 없다면, 시작 노드에서 끝 노드로 갈 수 없다는 것이 될 것입니다! 문제를 하나 풀어보겠습니다. 큐에 시작점인 0을 넣고, 0번을 방문 했다고 체크 합니다. 큐의 가장 위에 있는 0번 노드가 시작 노드가 됩니다.0번 노드가 가리키는 1번과 2번 노드를 큐에 ..

반응형