Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- LayerMark
- Object Pooling
- 프로그래머스
- 충돌위험 찾기
- Animation State Machine
- 오브젝트 풀링
- CSharp #자료구조
- Blend Type
- Back Tracking
- 너비 우선 탐색
- Algorithm
- ASTAR
- C#
- Lv2
- 깊이 우선 탐색
- Unity
- 플레이어 이동
- heap tree
- pccp 기출문제 2번
- pccp 기출문제 3번
- Ainimation Blending
- 플레이어 방향전환
- Hpbar
- Scrooling
- raycasting
- pccp 기출문제 1번
- Hp바
- 2D슈팅게임
- Object Poling
- 유니티
Archives
- Today
- Total
주녘공부일지
[프로그래머스 C#] Lv.3 등대 본문
https://school.programmers.co.kr/learn/courses/30/lessons/133500
1. 정답코드 및 핵심 아이디어, 유의사항
조건을 만족시키는 켜진 등대의 총 개수의 최소 값을 구하는 문제
- 등대를 노드(정점), 등대 간의 연결상태를 간선으로 둠
- 연결된 두 노드 중 하나는 무조건 켜져있어야 함
- 간선의 개수는 정점의 개수 - 1개, 모든 등대는 서로 연결된 길에 따라 서로 이동할 수 있음
-> 사이클을 이룰 수 없음 ( ex. a -> b, b -> c, c -> a )
- 최소 개수를 구하기 위해서는 초기에 존재하는 모든 리프노드는 불이 들어와선 안됨
-> 초기 리프노드와 연결된 노드는 무조건 불이 켜져야 함
풀이 방법 (BFS 알고리즘)
리프 노드를 최하위 노드로 보고, 자식(하위) 노드 -> 부모(상위) 노드 방향으로 탐색
-> 리프 노드에 대한 연산이 끝났다면 재탐색이 필요없으므로 자식 노드와 부모 노드의 연결을 끊어줌
-> 만약, 현재 탐색 대상인 노드가 리프 노드가 아니라면 연산 중인 다른 자식 노드를 가진 것
-> 리프 노드가 될 때까지 대기하기 위해 재탐색 대상으로 두고 다음 대상을 체크
https://godgjwnsgur7.tistory.com/47
주석 참조
using System;
using System.Collections.Generic;
public class Solution
{
public int solution(int n, int[,] lighthouse)
{
int answer = 0;
var boolArray = new bool[n + 1]; // 등대의 불이 켜져있는지
var dict = new Dictionary<int, List<int>>(); // 연결된 꺼진 등대
var queue = new Queue<int>(); // BFS 탐색을 위한 queue
for (int i = 1; i <= n; i++)
dict.Add(i, new List<int>());
// 간선 그래프 세팅
for (int i = 0; i < lighthouse.GetLength(0); i++)
{
dict[lighthouse[i, 0]].Add(lighthouse[i, 1]);
dict[lighthouse[i, 1]].Add(lighthouse[i, 0]);
}
// 초기에 존재하는 모든 리프 노드 번호 세팅
for (int i = 1; i <= n; i++)
if (dict[i].Count == 1)
queue.Enqueue(i);
while (queue.Count > 0)
{
// 연결된 두 등대 번호 n1, n2
int n1 = queue.Dequeue();
// 연결된 등대가 없을 경우
if (dict[n1].Count == 0)
continue;
// 리프노드가 아닐 경우 재탐색 대상으로 둠
if (dict[n1].Count != 1)
{
queue.Enqueue(n1);
continue;
}
// 리프노드라면 탐색을 이어가며 처리
int n2 = dict[n1][0];
dict[n1].Remove(n2);
dict[n2].Remove(n1);
if (boolArray[n1] == false)
boolArray[n2] = true;
queue.Enqueue(n2);
}
// 켜진 등대의 개수 구하기
foreach (bool b in boolArray)
if (b) answer++;
return answer;
}
}
'CodingTest > Programmers Lv.3' 카테고리의 다른 글
[프로그래머스 C#] Lv.3 부대 복귀 (1) | 2024.02.24 |
---|---|
[프로그래머스 C#] Lv.3 아이템 줍기 (0) | 2024.02.21 |
[프로그래머스 C#] Lv.3 110 옮기기 (0) | 2024.02.18 |
[프로그래머스 C#] Lv.3 순위 (0) | 2024.02.07 |
[프로그래머스 C#] Lv.3 이중우선순위큐 (0) | 2024.02.05 |