본문 바로가기
반응형

Problem Solving242

백준 2178번 미로 탐색 - 스위프트(Swift) 풀이 + 그림 설명 1. 1인 칸은 그래프의 정점으로 생각한다. 2. 인접한 칸이 1이면 그 칸으로 가는 간선을 추가한다. 3. 완성된 그래프에서 정점 (1, 1)에서 (N, M)으로 가는 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS를 사용한다. 1. 1인 칸은 그래프의 정점으로 생각한다. 현재 상황을 그래프로 나타낼 수 있다. 0인 칸은 어차피 갈 수 없는 칸이므로 무시하고, 1인 칸들을 정점이라고 생각하자. 2. 인접한 칸이 1이면 그 칸으로 가는 간선을 추가한다. 인접한 칸이 1이면 해당 칸으로 이동할 수 있다. 이것을 그래프에 표현해주면 인접한 칸으로 가는 간선을 추가하는 것과 같다. 3. 완성된 그래프에서 정점 (1, 1)에서 (N, M)으로 가는 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS를.. 2022. 1. 16.
백준 2630번 색종이 만들기 - 스위프트(Swift) 풀이 + 그림 설명 그림부터 너무 분할 정복처럼 생긴 분할 정복 문제. 1. 색종이를 4개로 쪼갠다. 2. 재귀적으로 4개의 조각에 대해 각각 하얀색과 파란색의 개수를 센다. 3. 4개 조각에서 구한 하얀색과 파란색의 개수를 더해 전체 개수를 구한다. 4. 만약 4개 조각이 모두 같은 색인 경우, 같은 색이 4개 있는 것이 아니라 큰 하나의 색종이인 것을 조심한다. 1. 색종이를 4개로 쪼갠다. 모두 같은 색이면 더 이상 자르지 말라고 했다. 하지만 생각을 달리해서 일단 자른 다음에, 모두 같은색이면 다시 붙일 것이다..! 2. 재귀적으로 4개의 조각에 대해 각각 하얀색과 파란색의 개수를 센다. 다음과 같은 함수를 정의했다. 전체 종이에서 (row, col)이 왼쪽 꼭짓점이고, 크기가 size인 조각 내의 (하얀색 수, 파.. 2022. 1. 16.
백준 1764번 듣보잡 - 스위프트(Swift) 풀이 Set의 메소드들이 너무 잘 구현되어 있어서 거저먹을 수 있는 문제. 1. 듣도 못한 사람들로 Set을 만든다. 2. 보도 못한 사람들로 Set을 만든다. 3. 듣도 보도 못한 사람을 두 집합의 intersection(_:)으로 구한다. 4. 듣도 보도 못한 사람을 sorted()로 정렬해서 사전 순으로 출력한다. 1. 듣도 못한 사람들로 Set을 만든다. 이 문제는 교집합을 구하는 문제이다. 딕셔너리나 이분탐색으로 직접 교집합을 구할 수도 있겠지만, 스위프트의 Set에는 이미 intersection 메소드가 있으니 편하게 이걸 사용하기 위해서 Set으로 만들어준다. 2. 보도 못한 사람들로 Set을 만든다. 1번과 마찬가지로 M명을 입력으로 받아 하나의 Set으로 만들어준다. 3. 듣도 못한 사람들도 .. 2022. 1. 16.
백준 1620번 나는야 포켓몬 마스터 이다솜 - 스위프트(Swift) 풀이 문제가 엄청 엄청 긴데, 마지막 오박사 말만 읽으면 된다. 1. 이름을 보고 번호를 말하기 위해 Dictionary를 둔다. 2. 번호를 보고 이름을 말하기 위해 Dictionary 또는 Array을 둔다. 1. 이름을 보고 번호를 말하기 위해 Dictionary를 둔다. N이 100,000이므로, 각 쿼리를 완전탐색으로 O(N)에 수행해서는 시간 안에 통과할 수 없다. Key가 포켓몬 이름이고 Value가 번호인 딕셔너리를 두어 O(1)에 각 쿼리를 완료해야 한다. 2. 번호를 보고 이름을 말하기 위해 Dictionary 또는 Array를 둔다. 1번이랑 같은데, Key, Value 타입만 반대로 하면 된다. Key가 Int인 경우에는 배열을 subscript로 접근하는 거랑 똑같기 때문에 배열로도 가.. 2022. 1. 16.
백준 12851번 숨바꼭질 2 - 스위프트(Swift) 풀이 1697번 숨바꼭질 문제에 추가로 경우의 수까지 출력해야 하는 문제. 1. 각 점을 정점이라고 생각한다. 2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가는 방향 간선 3개를 추가한다. 3. 정점 N에서 K까지의 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS로 쉽게 구할 수 있다. 4. BFS를 돌 때 이미 방문했던 곳이더라도 해당 정점을 N에서 최단거리로 온 경우라면, 또 방문해서 경우의 수를 카운트해준다. ↓ 1, 2, 3번에 대한 설명은 1697번 풀이를 확인 ↓ 백준 1697번 숨바꼭질 - 스위프트(Swift) 풀이 현재 상황을 그래프로 치환할 수 있음을 떠올리면 그 뒤로 구현은 쉽다. 1. 각 점을 정점이라고 생각한다. 2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가.. 2022. 1. 15.
반응형

티스토리툴바