카테고리 없음
[C#] 프로그래머스 BFS 연습 - 미로 탈출
굴러다니다니
2025. 3. 7. 17:15
https://school.programmers.co.kr/learn/courses/30/lessons/159993
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
진짜 푸는데 한시간 넘게 걸린듯,,,
아직 BFS가 익숙하지 못해서 인듯
풀이 과정
1. string[] 형태의 maps를 2차원 char 배열로 바꾸기 + 바꾸면서 S, L, E의 위치 표시해두기
2. S -> L 와 L->E로 나누기
3. BFS 구현하기
using System;
using System.Collections.Generic;
public class Solution {
public int solution(string[] maps) {
int[] start = new int[2];
int[] lever = new int[2];
int[] exit = new int[2];
char[,] changeMaps = new char[maps.Length, maps[0].Length];
// 맵 정보 저장 & 좌표 찾기
for (int i = 0; i < maps.Length; i++) {
for (int j = 0; j < maps[i].Length; j++) {
changeMaps[i, j] = maps[i][j];
if (maps[i][j] == 'S') {
start[0] = i; start[1] = j;
} else if (maps[i][j] == 'L') {
lever[0] = i; lever[1] = j;
} else if (maps[i][j] == 'E') {
exit[0] = i; exit[1] = j;
}
}
}
// 1️⃣ S → L 거리 구하기
int leverDist = BFS(start[0], start[1], lever[0], lever[1], changeMaps, maps.Length, maps[0].Length);
if (leverDist == -1) return -1;
// 2️⃣ L → E 거리 구하기
int exitDist = BFS(lever[0], lever[1], exit[0], exit[1], changeMaps, maps.Length, maps[0].Length);
if (exitDist == -1) return -1;
return leverDist + exitDist;
}
// ✅ BFS 함수: 최단 거리 찾기
private int BFS(int startX, int startY, int targetX, int targetY, char[,] changeMaps, int rows, int cols) {
int[,] distances = new int[rows, cols];
bool[,] visited = new bool[rows, cols];
Queue<(int, int)> queue = new Queue<(int, int)>();
queue.Enqueue((startX, startY));
visited[startX, startY] = true;
int[] dx = { 1, 0, -1, 0 };
int[] dy = { 0, 1, 0, -1 };
while (queue.Count > 0) {
var (x, y) = queue.Dequeue();
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX < 0 || newY < 0 || newX >= rows || newY >= cols) continue;
if (changeMaps[newX, newY] == 'X' || visited[newX, newY]) continue;
visited[newX, newY] = true;
distances[newX, newY] = distances[x, y] + 1;
queue.Enqueue((newX, newY));
if (newX == targetX && newY == targetY) {
return distances[newX, newY];
}
}
}
return -1; // 도달할 수 없는 경우
}
}
728x90
반응형