본문 바로가기

Algorithm236

[Swift][BFS] 백준 10026 (적록색약) 요구능력 : BFS 코드설명 : 이 문제의 핵심 1) 그림이 몇 개의 구역으로 나눠져있다. 2) 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. 3) 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 우리가 구해야하는건 구역의 수이다. 그렇다는건 BFS 또는 DFS 함수를 한 번 호출할 때 인접한부분을 탐색하면서 같은 색상인 경우에 방문처리를 하면된다. 다른 색상인 경우에는 큐에 넣지 않음으로써 탐색을 하지않는다. 그렇게 모든 배열의 인덱스를 시작점으로 사용해서 방문처리 안된곳만 탐색할 때, 탐색하는 횟수가 곧 구역의 개수이다. 이미 방문처리된 곳은 횟수에 세어진 구역이기 때문이다. 적록색약의 경우 하나의 배열을 더 만들어서 R을 G로 치환하여 똑같이 BFS를 탐색하며 .. 2022. 1. 25.
[Swift][BFS] 백준 1963번 (소수 경로) 요구능력 : BFS && 에라토스테네스의 체 코드설명 : 이 문제의 핵심 1) 비밀번호를 한 번에 한자리 밖에 못바꾼다. 2) 1000이상 9999이하의 범위만 가능하다. 3) 소수로만 단계를 거쳐야한다. 두 소수 사이의 변환에 필요한 최소 회수를 출력한다고 했으므로, BFS를 의심해본다. 1) 비밀번호를 한 번에 한자리 밖에 못바꾼다. 이 조건이 이 문제의 핵심인데, 비밀번호를 한 번에 한자리 바꾼다고 했으므로, 입력받은 수가 있으면 천의자리를 바꿔서 큐에넣고, 백의자리를 바꿔서 큐에넣고, 십의자리를 바꿔서 큐에넣고, 일의자리를 바꿔서 큐에넣는다. 이렇게 BFS로 풀어주면 된다는 생각이 들었다. 처음 큐에 입력받은 숫자를 넣은 뒤, 그 숫자의 천의자리, 백의자리, 십의자리, 일의자리를 추출해서 배열에 .. 2022. 1. 25.
[Swift][BFS] 백준 16236 (아기상어) 요구능력 : BFS(이전 방문 좌표와 거리비교) 코드설명 : 이 문제에서 핵심 1. 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 2. 아기상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다. 3. 아기상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 4. 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 5. 더 이상 먹을 수 있는 물고기가 없다면 아기상어는 엄마상어에게 도움을 요청한다.(종료조건) 6. 먹을 수 있는 물고기가 1마리보다 많다면 거리가 가장 가까운 물고기를 먹으러 간다 7. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그런 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 8. 아기 상어는 자신의 크기와 같은 .. 2022. 1. 22.
[Swift][DFS][BFS] 백준 16947번 (서울 지하철 2호선) 요구능력 : DFS & BFS 코드설명 : 이 문제에서 요구하는 핵심사항 1. 인접리스트 2. 순환선 3. 역과 순환선 사이의 거리 1. 인접리스트 인접리스트는 해당 인덱스번호와 이어진 노드들을 해당인덱스의 배열에 넣으면 완성된다. 정점과 간선이 주어진다면 인접리스트를 생각하는 습관을 들이는게 좋다. var graph : [[Int]] = Array(repeating: [], count: n + 1) for _ in 0.. 2 -> 3 -> 1 과 같은경우 순환선이다. 하지만 주의할 점이 있다. 1 -> 2 -> 1 과 같은경우에는 순환선이 될 수 없다. 그림으로 그려보면 알것이다. 순환선이 아닌 그냥 일직선이라는것을.. 위의 설명으로봤을때 도출한결과 시작노드와 현재노드가 같아지면 순환선이 되지만, 1.. 2022. 1. 20.

티스토리툴바