111. 무인도 여행

 

기본 틀 :

 

using System;

public class Solution {
    public int[] solution(string[] maps) {
        int[] answer = new int[] {};
        return answer;
    }
}

 

문제를 보고 DFS나 BFS로 maps를 탐색 및 bool 타입 변수로 방문 여부를 남겨 다시 탐색하지 못 하게 만들어 값을 구하고자 했다.

 

DFS를 사용하기 위해 메서드의 매개변수를 고민한 결

 

    // 필요한 매개변수
    // 방문 여부
    // 지도
    // 현재 세로 위치
    // 현재 가로 위치
    public int DFS(bool[,] visited, string[] maps, int currentRow, int currentColum)
    {

    }

 

위와 같이 방문 여부, 지도, 현재 세로 위치, 현재 가로 위치가 매개변수로 필요하다고 판단했다.

 

그리고 메인 메서드에는

 

    public int[] solution(string[] maps) {
        List<int> list = new List<int>();
        bool[,] visited = new bool[maps.Length, maps[0].Length];
        
        if(list.Count == 0) return new int[] { -1 };
        
        return list.OrderBy(element=>element).ToArray();
    }

 

List를 만들어 가변적인 결과를 담기 위해 준비하고

 

List의 개수가 0이면 -1, 그 밖에는 오름차순된 정수형 배열을 반환할 수 있게 만들어줬다.

 

그 다음으로

 

        for(int i = 0; i < maps.Length; i++)
        {
            for(int j = 0; j < maps[0].Length; j++)
            {
                if(maps[i][j] == 'X') continue;
                int sum = DFS(visited, maps, i, j);
                if(sum != 0)list.Add(sum);
            }
        }

 

당장에 maps에서 'X'를 피해 탐색할 방법이 존재하지 않기 때문에

 

2중 반복문으로 'X'일 경우 스킵하고, 아닐 경우 DFS의 결과를 담을 수 있게 해줬다.

 

DFS 내부에는

    // 필요한 매개변수
    // 방문 여부
    // 지도
    // 현재 세로 위치
    // 현재 가로 위치
    public int DFS(bool[,] visited, string[] maps, int currentRow, int currentColum)
    {
        int sum = 0;
        if(!visited[currentRow, currentColum] && maps[currentRow][currentColum] != 'X')
        {
            visited[currentRow, currentColum] = true;
            //Console.WriteLine("currentRow : "+currentRow+", currentColum : "+currentColum+", maps : "+maps[currentRow][currentColum]);
            sum += int.Parse(maps[currentRow][currentColum].ToString());
            if((currentRow - 1) > -1)  sum += DFS(visited, maps, currentRow - 1, currentColum);
            if((currentRow + 1) < maps.Length)  sum += DFS(visited, maps, currentRow + 1, currentColum);
            if((currentColum - 1) > -1)  sum += DFS(visited, maps, currentRow, currentColum - 1);
            if((currentColum + 1) < maps[currentRow].Length)  sum += DFS(visited, maps, currentRow, currentColum + 1);
        }
        //Console.WriteLine("sum : "+sum);
        return sum;
    }

 

방문한 곳과 'X'을 피해 더한 값을 구하고 상하좌우로 이동이 가능한 범위일 경우 이동을 시켜 다음 계산을 진행시켰다.

 

전체 코드 : 

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string[] maps) {
        List<int> list = new List<int>();
        bool[,] visited = new bool[maps.Length, maps[0].Length];
        
        for(int i = 0; i < maps.Length; i++)
        {
            for(int j = 0; j < maps[0].Length; j++)
            {
                if(maps[i][j] == 'X') continue;
                int sum = DFS(visited, maps, i, j);
                if(sum != 0)list.Add(sum);
            }
        }
        
        if(list.Count == 0) return new int[] { -1 };
        
        return list.OrderBy(element=>element).ToArray();
    }
    
    // 필요한 매개변수
    // 방문 여부
    // 지도
    // 현재 세로 위치
    // 현재 가로 위치
    public int DFS(bool[,] visited, string[] maps, int currentRow, int currentColum)
    {
        int sum = 0;
        if(!visited[currentRow, currentColum] && maps[currentRow][currentColum] != 'X')
        {
            visited[currentRow, currentColum] = true;
            //Console.WriteLine("currentRow : "+currentRow+", currentColum : "+currentColum+", maps : "+maps[currentRow][currentColum]);
            sum += int.Parse(maps[currentRow][currentColum].ToString());
            if((currentRow - 1) > -1)  sum += DFS(visited, maps, currentRow - 1, currentColum);
            if((currentRow + 1) < maps.Length)  sum += DFS(visited, maps, currentRow + 1, currentColum);
            if((currentColum - 1) > -1)  sum += DFS(visited, maps, currentRow, currentColum - 1);
            if((currentColum + 1) < maps[currentRow].Length)  sum += DFS(visited, maps, currentRow, currentColum + 1);
        }
        //Console.WriteLine("sum : "+sum);
        return sum;
    }
}

 

생각보다 간단한 문제였지만 DFS나 BFS를 재귀형식으로 짜는데 익숙지 않아서 오랜 시간이 걸렸다...