본문 바로가기

문과 코린이의, [C#] 기록/C# CodingTest

[문과 코린이의 IT 기록장] C# 프로그래머스(Programmers) - 무인도 여행

반응형

[문과 코린이의 IT 기록장] C# 프로그래머스(Programmers) - 무인도 여행

[문과 코린이의 IT 기록장] C# 프로그래머스(Programmers) - 무인도 여행

 


 

코딩테스트 연습 | 프로그래머스 스쿨

개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요!

school.programmers.co.kr


1. Problem

1) 문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

2) 제한 사항

  • 3 ≤ maps의 길이 ≤ 100
    • 3 ≤ maps[i]의 길이 ≤ 100
    • maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
    • 지도는 직사각형 형태입니다.

3) 입출력 예

maps result
["X591X","X1X5X","X231X", "1XXX1"] [1, 1, 27]
["XXX","XXX","XXX"] [-1]

4) 입출력 예 설명

(1) 입출력 예

위 문자열은 다음과 같은 지도를 나타냅니다.

연결된 땅들의 값을 합치면 다음과 같으며

이를 오름차순으로 정렬하면 [1, 1, 27]이 됩니다.

 

(2) 입출력 예 

위 문자열은 다음과 같은 지도를 나타냅니다.

섬이 존재하지 않기 때문에 -1을 배열에 담아 반환합니다.


2. Solution

1) 내가 푼 정답 1

using System;
using System.Collections.Generic; 

public class Solution {
    static int row = 0;
    static int col = 0;
    static int[,] land;

    static int[] dx = { 0, 0, 1, -1 };
    static int[] dy = { 1, -1, 0, 0 };
    
    
    public int[] solution(string[] maps) {
        row = maps.Length;
        col = maps[0].Length;

        land = new int[row, col];

        return StayLand(SetLand(maps));
    }
    
    
    static int[,] SetLand(string[] maps)
    {
        for (int r = 0; r < row; r++)
        {
            for (int c = 0; c < col; c++)
            {
                if (char.Parse(maps[r].Substring(c, 1)) == 'X') land[r, c] = -1;
                else land[r, c] = int.Parse(maps[r].Substring(c, 1));
            }
        }
        return land;
    }
    
    
    static int[] StayLand(int[,] land)
    {
        List<int> answer = new List<int>();

        for (int r = 0; r < row; r++)
        {
            for (int c = 0; c < col; c++)
            {
                int Sum = DFSLand(r, c);
                if (Sum > 0) answer.Add(Sum);
            }
        }

        // 무인도가 없는 경우
        if (answer.Count == 0) answer.Add(-1);

        answer.Sort();
        return answer.ToArray();
    }
    
    
    static int DFSLand(int dfs_row, int dfs_col)
    {
        // 배열의 범위를 벗어났을 경우
        if (dfs_row < 0 || dfs_col < 0 || dfs_row >= row || dfs_col >= col) return 0;

        // 이미 방문한 곳이라면 return
        if (land[dfs_row, dfs_col] == -1) return 0;

        int Sum = land[dfs_row, dfs_col];
        land[dfs_row, dfs_col] = -1; // 방문 상태 저장

        for (int idx = 0; idx < 4; idx++)
        {
            Sum += DFSLand(dfs_row + dx[idx], dfs_col + dy[idx]);
        }

        return Sum;
    }
}

2) 다른 사람 풀이 참고 1

using System;
using System.Collections.Generic; 

public class Solution {
   
    public int[] solution(string[] maps) {
        List<int> answer = new List<int>();
            bool[,] visited = new bool[maps.Length, maps[0].Length];
            int tempValue = 0;

            for (int iPos = 0; iPos < maps.Length; iPos++, tempValue = 0)
            {
                for (int jPos = 0; jPos < maps[iPos].Length; jPos++)
                {
                    tempValue = VisitCheck(new Point(iPos,jPos), maps,ref visited);
                    if (tempValue > 0) answer.Add(tempValue);
                }
            }

            answer.Sort();

            return answer.Count == 0 ? new int[1] { -1 } : answer.ToArray();
    }
    
      class Point
        {
            public int X;
            public int Y;

            public Point(int x, int y)
            {
                this.X = x;
                this.Y = y;
            }

            public bool Check(string[] maps)
            {
                return X < 0 || Y < 0 || X > maps.Length - 1 || Y > maps[0].Length - 1;
            }
        }

        private static int VisitCheck(Point point, string[] maps, ref bool[,] visited)
        {
            if (point.Check(maps)) return 0;
            else if (visited[point.X, point.Y] || maps[point.X][point.Y].Equals('X')) return 0;
            else
            {
                visited[point.X, point.Y] = true;

                return maps[point.X][point.Y].Equals('X') ? 0 : int.Parse(maps[point.X][point.Y].ToString())
                    + VisitCheck(new Point(point.X - 1, point.Y), maps, ref visited)
                    + VisitCheck(new Point(point.X + 1, point.Y), maps, ref visited)
                    + VisitCheck(new Point(point.X, point.Y - 1), maps, ref visited)
                    + VisitCheck(new Point(point.X, point.Y + 1), maps, ref visited);
            }
        }
    
}

 

반응형