[C#] 프로그래머스 BFS 연습 - 미로 탈출

https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

진짜 푸는데 한시간 넘게 걸린듯,,,

아직 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; // 도달할 수 없는 경우
    }
}