bfs28 [Swift][프로그래머스][그래프] 가장 먼 노드 요구능력 넓이우선탐색(BFS) + 그래프 문제풀이 항상 그래프문제에서는 간선이 주어지면 인접리스트를 만들어야된다. 나는 graph 프로퍼티에 2차원배열로 인접리스트를 만들었다. 이렇게 만들면 graph[1] = [2, 3]과 같이 1번노드는 2번과 3번과 연결되어있다고 저장할 수 있다. 여기서 1번노드를 타고 2번노드를 들어가면 그대로 1번이 또 있게된다. 이 부분은 visited로 방문처리를 함으로써 재방문하지 않게해줄것이다. 문제에서 최단경로로 이동해야된다고 했다. 최단경로하면 가장 먼저 생각나는 알고리즘은 BFS이다. BFS를 사용해서 노드를 탐색하는데, 1번노드에서 가장 먼 노드의 개수를 찾아야되므로, maxCount변수에 가장 먼 거리를 저장해줬다. moveCntArr에는 거리에있는 노드를 구해.. 2022. 5. 2. [Swift][BFS] 백준 1600번 (말이 되고픈 원숭이) 요구능력 BFS 문제풀이 기본적인 BFS에서 우리는 최소의 이동횟수를 구해야한다. 어느부분에서 점프했을때 최소의 이동거리인지 알 수 있는 방법이 없기 때문에 BFS를 돌아주면서 방문하는 곳마다 점프하는 경우를 큐에 넣어준다. 이때 점프횟수가 남아있을 때만 점프를 해준다. 이 문제에서 가장 핵심포인트는 3차원 배열을 사용해서 한 지점에 도착했을 때 몇번의 점프가 남았는지를 적어주는 것이다. 무슨 말이냐면 만약 내가 점프를 한번도안하고 (0,0)부터 (x,y)까지 이동했을 경우가 있고, 점프를 한번하고 (x,y)까지 이동했을 경우가 있다고 가정해보자. 근데 같이 방문처리를 해줘버리면, 이게 겹치게된다. 따로 관리하기위해서 3차원으로 방문처리를 해주게된것이다. 그리고 도착지점에 도착했을 때 바로 break를 .. 2022. 4. 8. [Swift][BFS] 백준 16954번 (움직이는 미로 탈출) 요구능력 BFS와 level별로 BFS를 확인할 수 있는지 문제풀이 접근법은 뭔가 대놓고 BFS이다. 처음 접근할때 다들 접근법이 가지각색일 것같다. 이 문제는 시간이라는 요소가 정말 중요한 문제이다. 이 문제를 풀기전에 3차원 배열에 대해 간단히 짚고 넘어가야한다. 우선, 3차원 배열은 arr[][][]이렇게 표현하는데 arr[면][행][열]로 보면된다. 이 문제에서는 면은 시간으로 볼것이다. 시간별로 행열의 방문여부를 확인하는 이유는 중복을 없애기 위함이다. 벽의 위치가 같을 때 같은지점을 중복해서 방문하면 시간낭비만 되는 비효율적인 코드가 된다. 벽은 시간에 따라서 움직인다. 따라서 시간에 따라 방문할 수 있는 위치도 초기화해줘야 한다. 그래야 자기자신의 위치에도 중복없이 방문이 가능하다. 나름 중.. 2022. 3. 23. [Swift][BFS] 백준 9376번 (탈옥) 요구능력 : 0-1 BFS알고리즘 코드설명 : 이 문제는 다익스트라로도 풀린다고 하고 0-1 BFS알고리즘 으로도 문제가 풀린다. 나는 0-1 BFS알고리즘으로 공부하고 여러군데를 참고해서 문제를 풀어봤다. 나는 처음에 죄수 2명으로 BFS를 해서 문을 최소로 구하고 탈출시켜봤는데, 예제 입력 5 9에서는 성공했지만 예제 입력 5 11에서는 성공못했다. 답은 0 이지만 내 출력은 1이 나와서인데, 내 출력이 1이 나온이유는 위에 있는 문을 부수면 가장자리(x == 0 or y == 0 or x == h or y == h)로 올경우 종료조건을 줬기 때문이다. 문을 부수더라도 가장최소한으로 움직이는 방법이 되버린것이다. 예제 입력 5 11에서 성공하려면 무조건 가장자리에 간다고해서 종료조건이라는걸 만들면 안.. 2022. 2. 28. 이전 1 2 3 4 ··· 7 다음
