너비우선탐색18 [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] 백준 12906번 (새로운 하노이 탑) 요구능력 : Set, BFS 코드설명 : 원판움직이는 경우를 BFS로 표현하는것은 어렵지 않다. A에 원판이 있는경우 하나를 빼서 B에 넣는경우를 큐에 넣어주고 C에 넣는경우를 큐에 넣어주면된다. B와 C도 마찬가지로 하면된다. 이 문제에서 가장 중요한점은 방문처리를 어떻게 하느냐이다. 나는 처음에 방문처리를 안했다가 무한루프에 빠지고 말았다. 이런문제를 나처럼 처음 접하는 사람들은 당황하게 될 것이다. 방문처리를 해야되는데,, 문자열이네? 여태 좌표만 방문처리해봐서 문자열은 할줄 모르겠다 싶었다. Set을 활용하면 되더라. 다른 언어들은 Set에 큐에 사용한 형식그대로 사용하는데, Swift는 따로 custom을 해줘야한단다. 그냥 String으로 처리해줘야겠다. 각 모든 배열을 joined()로 st.. 2022. 2. 16. [Swift][BFS] 백준 2234번 (성곽) 요구능력 : BFS 코드설명 : 1) 이 성에 있는 방의 개수 BFS를 도는 횟수가 방의 개수가 되겠다. BFS를 한번 돌게되면 벽에 막혀서 방문이 끝나게 된다. 방문하지 않은 곳의 배열을 모두 돌면서 방문처리를 해준다면 bfs를 도는 수 만큼이 방의 개수가 되겠다. 2) 가장 넓은 방의 넓이 큐에 append할 때 마다 방의 넓이는 count를 증가시켜줘야한다. 큐에 넣을때마다 증가시켜주지 않고 큐에 이동횟수를 붙여서 세게되면 모든 칸의 수를 다 세야하는데 아래와 같이 모든 경우의 수를 세지 못한다. 3) 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 마찬가지로 2진수를 이용하여 있는 벽만 하나씩 지워보면서 arr을 전부 돌아보면된다. 후기 : 생각도 못한 &연산.. 비트연산문제를 한번도 안.. 2022. 2. 3. 이전 1 2 3 4 5 다음
