[TIL] C# 공부 - json 파일 관리, DFS/BFS 등
📕학습 개요
유니티 캠프 8일차.
오늘은 C# 강의 5주차 내용을 복습하고, 숙제로 나온 알고리즘 문제 중 남은 두개를 풀어봤다. 오후에는 TRPG의 도전 기능을 구현해보았다.
📖학습 내용
알고리즘 문제
Flood Fill
Flood Fill 알고리즘은 2D 격자(grid) 에서 시작점으로부터 같은 값을 가진 영역을 탐색하면서 새로운 값으로 바꾸는 알고리즘으로, 굉장히 유명한 탐색 문제라고 한다.
문제는 다음과 같다.
- LeetCode 733번 기준
- 2D 배열
image와 좌표(sr, sc)그리고 색깔newColor가 주어졌을 때,(sr, sc)에서 시작해서 상하좌우 인접한 같은 색의 픽셀들을 전부newColor로 바꾸는 함수 구현.
구현 자체는 생각보다 어렵지 않았던 것 같다. 현재 노드의 색을 체크한 뒤, 근접한 노드로 전이되는 재귀함수로 만들면 좋겠다 싶었는데 자연스럽게 DFS 탐색으로 구현된 것 같다.
구현 코드
class Program
{
static int[][] FloodFill(int[][] image, int sr, int sc, int newColor)
{
int originalColor = image[sr][sc]; //원래 색
//색이 같으면 바꿀 필요 없음
if(originalColor == newColor)
{
return image;
}
ChangeColor(image, sr, sc, originalColor, newColor);
return image;
}
static void ChangeColor(int[][] image, int x, int y, int originalColor, int newColor)
{
//범위 벗어나면 리턴
if(x < 0 || y < 0 || x >= image.Length || y >= image[0].Length)
return;
//다른 색이면 리턴
if (image[x][y] != originalColor)
return;
//색 변경
image[x][y] = newColor;
//상하좌우 재귀 호출
ChangeColor(image, x + 1, y, originalColor, newColor);
ChangeColor(image, x - 1, y, originalColor, newColor);
ChangeColor(image, x, y + 1, originalColor, newColor);
ChangeColor(image, x, y - 1, originalColor, newColor);
}
static void Main(string[] args)
{
int[][] image = new int[3][];
image[0] = new int[] { 1, 1, 1 };
image[1] = new int[] { 1, 1, 0 };
image[2] = new int[] { 1, 0, 1 };
int[][] result = FloodFill(image, 1, 1, 2);
foreach(int[] x in result)
{
foreach (int y in x)
{
Console.Write(y);
}
Console.WriteLine();
}
}
}
Longest Increasing Subsequence(LIS)
이번에도 유명한 DP(Dynamic Programming) 과 이분 탐색 문제로, 나는 동적 프로그래밍 느낌으로 풀어보았다.
문제는 다음과 같다.
- 주어진 정수 배열에서 오름차순으로 증가하는 부분 수열 중 가장 긴 길이를 구하라.
- 예시
Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: 가장 긴 오름차순 부분 수열은 [2, 3, 7, 101]
구현 코드
class Program
{
static int LengthOfLIS(int[] nums)
{
if(nums.Length == 0)
{
return 0;
}
int n = nums.Length;
int[] arrLength = new int[n]; //각 LIS 길이를 저장
Array.Fill(arrLength, 1); //전부 최소 1의 길이를 가짐
//각 위치에서 끝나는 LIS 길이를 저장하는 방식
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
{
if (nums[j] < nums[i])
{
arrLength[i] = Math.Max(arrLength[i], arrLength[j] + 1);
}
}
}
return arrLength.Max();
}
static void Main(string[] args)
{
int[] input = { 10, 9, 2, 5, 3, 7, 101, 18 };
Console.WriteLine(LengthOfLIS(input));
}
}
시간복잡도가 O(n²)으로 나오는데, 이분 탐색을 사용하면 (O(n log n))으로 줄일 수 있다고 한다. 하지만 나는 아직 이분 탐색을 제대로 사용할 줄 몰라서 일단은 이렇게 푸는 게 최선인 듯 하다. 이 문제는 추후에 이분 탐색을 공부한 뒤 다시 풀어봐야겠다.
DFS , BFS
DFS(Depth-First Search, 깊이 우선 탐색)와 BFS(Breadth-First Search, 너비 우선 탐색)는 그래프를 탐색하는 대표적인 알고리즘이다. 두 방식은 탐색의 순서와 자료구조 사용 방식에서 차이가 있다.
-
DFS (깊이 우선 탐색)
- 개념: 한 노드를 선택해서 가능한 깊숙이 들어가며 탐색한 후, 더 이상 갈 곳이 없으면 이전 노드로 되돌아가 다른 경로를 탐색합니다.
- 자료구조: 스택(Stack) 또는 재귀(Recursive Function)를 사용
-
BFS (너비 우선 탐색)
- 개념: 시작 노드에서 인접한 모든 노드를 먼저 탐색한 뒤, 그 다음 깊이의 노드들을 탐색합니다.
- 자료구조: 큐(Queue)를 사용
예제 코드(인접 리스트 기반)
using System;
using System.Collections.Generic;
class GraphTraversal
{
// 그래프는 Dictionary를 이용해 인접 리스트로 표현
static Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
// DFS 구현 (재귀)
static void DFS(int node, HashSet<int> visited)
{
// 방문 처리
visited.Add(node);
Console.Write($"{node} ");
// 인접한 노드들을 재귀적으로 방문
foreach (int neighbor in graph[node])
{
if (!visited.Contains(neighbor))
{
DFS(neighbor, visited);
}
}
}
// BFS 구현 (큐 사용)
static void BFS(int startNode)
{
Queue<int> queue = new Queue<int>();
HashSet<int> visited = new HashSet<int>();
// 시작 노드 큐에 추가 및 방문 처리
queue.Enqueue(startNode);
visited.Add(startNode);
while (queue.Count > 0)
{
int current = queue.Dequeue();
Console.Write($"{current} ");
foreach (int neighbor in graph[current])
{
if (!visited.Contains(neighbor))
{
queue.Enqueue(neighbor);
visited.Add(neighbor);
}
}
}
}
static void Main()
{
// 그래프 구성
graph[1] = new List<int> { 2, 3 };
graph[2] = new List<int> { 1, 4, 5 };
graph[3] = new List<int> { 1 };
graph[4] = new List<int> { 2 };
graph[5] = new List<int> { 2 };
Console.WriteLine("DFS (Depth-First Search):");
DFS(1, new HashSet<int>()); // 시작 노드: 1
Console.WriteLine("\n\nBFS (Breadth-First Search):");
BFS(1); // 시작 노드: 1
}
}
C#의 디폴트 접근 제한자
TRPG를 만들다가 필드나 클래스의 디폴트 제한자가 정확히 어떻게 되는지 잘 모르겠어서 한번 정리해 봤다.
| 대상 | 디폴트 접근 제한자 | 설명 |
|---|---|---|
| 클래스 | internal |
같은 어셈블리 내에서만 접근 가능 |
| 클래스 멤버(필드, 메서드, 속성 등) | private |
선언된 클래스 내부에서만 접근 가능 |
| 인터페이스 멤버 | public(강제) |
모든 인터페이스 멤버는 자동으로 public |
| enum | public |
모든 enum 값은 기본적으로 public |
🎮프로젝트 - TRPG 구현
오늘 구현한 기능은 다음과 같다.
- 아이템 정보를 구조체로 구현
- 아이템 데이터베이스를
JSON파일로 정리 - 마을에서 휴식 기능 추가
- 아이템 중복 장착 불가(부위별로)
- 던전 입장 기능 추가
- 게임 오버 추가
JSON 파일로 아이템 데이터 관리
원래는 아이템 데이터베이스를 담는 static class를 만들고, 그 안에 static 객체를 집어넣어서 데이터를 관리했는데, 이는 정적 데이터가 너무 많이 발생하기도 하고, 데이터가 코드 내부에 포함되어서 지저분할 뿐더러 유지보수가 어려운 부분이 있다.
튜터님께 조언을 구한 결과, JSON 을 사용하여 데이터를 분리해보기로 했다.
- JSON 파일 구조
[
{
"name": "스파르타의 갑옷",
"description": "전설의 갑옷입니다.",
"price": 3500,
"itemType": "Equipment",
"equipmentType": "Armor",
"statType": "방어력",
"stat": 15
}
]
- 로딩 코드
string json = File.ReadAllText("EquipItemDatabase.json");
JSON을 처음 써봤는데 생각보다 사용법이 간단해서 놀랐다. 이런 식으로 데이터 파일을 분리해서 작업하면 유지보수도 쉬워지고, 무엇보다 협업 시 큰 도움이 될 것 같다.
파일을 읽어오는데 실패하는 상황도 대비하여 null 예외처리도 해주었다.
try //null 예외처리
{
string json = File.ReadAllText("EquipItemDatabase.json");
var options = new JsonSerializerOptions
{
Converters = { new JsonStringEnumConverter() }
};
var loadedItems = JsonSerializer.Deserialize<List<ItemData>>(json, options);
if (loadedItems != null)
{
Items = loadedItems;
}
else
{
Console.WriteLine("JSON 파일 오류 발생");
Items = new List<ItemData>();
}
}
catch (Exception ex)
{
Console.WriteLine($"아이템 데이터 로드 중 오류 발생: {ex.Message}");
Items = new List<ItemData>();
}
아이템 중복 착용 방지
원래는 소유하고 있는 아이템이면 제한 없이 전부 착용가능했는데, 각 부위별 하나의 아이템만 장착 가능하도록 개선해보았다.
일단 인벤토리 클래스에서 플레이어가 장착중인 아이템을 담는 배열을 하나 만들었다.
public Equipment[] equippedItems { get; private set; } //플레이어가 장비중인 아이템
배열의 크기는 장착 가능한 아이템 타입의 개수에 맞추면 된다. 아직은 방어구, 무기 두 종류밖에 없기에 배열의 크기는 2면 충분하다.
그리고 아이템을 장착하는 과정에서 동일한 부위의 아이템을 장착하고 있는지 확인해주면 된다. 아이템 타입이 열거형으로 구현된 점을 활용하여 인덱스로 사용했다.
Equipment selected = equipments[playerInput - 1];
int equipIndex = (int)selected.EquipmentType;
if (selected.isEquipped) //이미 장착된 경우
{
selected.UnEquip(); //장착 해제
equippedItems[equipIndex] = null;
}
else
{
//같은 종류 장비가 이미 장착되어 있으면 해제
if (equippedItems[equipIndex] != null)
{
equippedItems[equipIndex].UnEquip();
}
selected.Equip();
equippedItems[equipIndex] = selected;
}
🏁오늘 배운 핵심 한줄 요약
- DFS는 스택 + 재귀, BFS는 큐
- 클래스 멤버의 디폴트 접근 제한자는 private
- 파일을 불러올 경우 예외처리를 꼭 해주자
- 데이터를 분리하는 편이 유지보수에 훨씬 유리하다
댓글남기기