반응형 그래프7 프로그래머스 빛의 경로 사이클 - C++ 풀이 1. 기존의 노드를 도착한 빛의 방향에 따라 4개의 노드로 쪼갠다. 2. 그리드의 문자열 값에 따라 방향 간선을 추가한다. 3. DFS로 모든 노드를 방문하면서 사이클을 모두 찾아낸다. 1. 기존의 노드를 도착한 빛의 방향에 따라 4개의 노드로 쪼갠다. 노드에 빛이 도달할 때 4가지 경우가 있다. 북쪽에서 도달한 경우, 동쪽에서 도달한 경우, 남쪽에서 도달한경우, 서쪽에서 도달한 경우. 이 4가지 경우는 모두 다른 경우이기 때문에 기존 노드들을 모두 4개로 쪼개서 도달한 빛의 방향에 따라 다른 노드로 보자. 2. 그리드의 문자열 값에 따라 방향 간선을 추가한다. 이제 그리드의 문자열 값에 따라 방향 간선을 추가하여 그래프를 완성한다. L, R인 경우 방향을 전환해주고, 해당 방향으로 1만큼 떨어진 노드로.. 2023. 9. 16. 백준 2224번 명제 증명 - C++ 풀이 1. 전건과 후건을 각각 그래프의 노드로 생각하고, 전건에서 후건으로 가는 간선을 추가한다. 2. 만약 정점 P에서 정점 Q로 가는 경로가 존재한다면 P => Q를 증명할 수 있다. 3. 플로이드와샬을 사용하여 모든 순서쌍 (p, q)에 대해 p에서 q로 가는 경로가 있는지 확인한다. 1. 전건과 후건을 각각 그래프의 노드로 생각하고, 전건에서 후건으로 가는 간선을 추가한다. 주어지는 명제들의 전건과 후건을 각각 그래프의 노드라고 생각하자. 그리고 전건과 후건을 방향 간선(전건->후건)으로 잇는다. 2. 만약 정점 P에서 정점 Q로 가는 경로가 존재한다면 P => Q를 증명할 수 있다. 완성된 그래프에서 만약 정점 P에서 정점 Q로 가는 경로가 존재한다면, P => Q를 증명할 수 있다는 의미이다. 3... 2023. 8. 21. 백준 10026번 적록색약 - 스위프트(Swift) 풀이 1. 그리드의 각 칸을 그래프의 정점으로 생각한다. 2. 인접한 칸의 색이 같은 색이면 간선으로 연결한다. 3. 어떤 칸을 시작점으로 DFS/BFS를 하면 해당 칸이 속하는 구역 내의 모든 칸을 방문할 수 있다. 4. 따라서 DFS/BFS의 호출 횟수가 곧 구역의 개수이다. 5. 적록색약인 경우 그리드의 R과 G를 같은 색으로 취급해준다. 1. 그리드의 각 칸을 그래프의 정점으로 생각한다. 그리드 전체를 그래프로 생각할 수 있다. 각 칸을 정점으로 둔다. 2. 인접한 칸의 색이 같은 색이면 간선으로 연결한다. 상하좌우로 인접한 칸이 같은 색이면 같은 구역이므로, 간선으로 연결해준다. 이러면 같은 구역인 정점끼리만 간선으로 연결될 것이다. 3. 어떤 칸을 시작점으로 DFS/BFS를 하면 해당 칸이 속하는 .. 2022. 1. 18. 백준 2667번 단지번호붙이기 - 스위프트(Swift) 풀이 + 그림 설명 1. 각 집을 그래프의 정점으로 생각한다. 2. 어떤 집을 시작점으로 DFS/BFS를 하면 해당 집이 속하는 단지 내의 모든 집을 방문할 수 있다. 3. 따라서 DFS/BFS의 호출 횟수가 곧 단지의 개수이고, 4. DFS/BFS를 돌면서 방문한 정점의 수가 한 단지 내에 속한 집의 수이다. 1. 각 집을 그래프의 정점으로 생각한다. 0인 곳은 갈 수 없으므로 무시하고, 1인 곳을 정점이라고 생각한다. 2. 어떤 집을 시작점으로 DFS/BFS를 하면 해당 집이 속하는 단지 내의 모든 집을 방문할 수 있다. (1, 1)을 시작점으로 그래프를 탐색해주면, 해당 단지 내의 모든 집을 방문할 수 있다. 탐색 방법은 DFS/BFS를 쓰면 된다. 이때 연결되지 않은 (1,4)와 (2,4)가 속한 단지는 방문을 하지.. 2022. 1. 17. 백준 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. 이전 1 2 다음 반응형
