[CodinGame] THERE IS NO SPOON - EPISODE 1(2차원 노드 찾기)

이번 게임은 제목부터 설명, 연출까지 모두 영화 <매트릭스>에서 가져왔습니다. There is no spoon'은 영화에서 나 온 대사로, 현실에서 일어나기 힘든 일이라고 믿는 것은 사실 우리 마음속의 관념에 지나지 않는다는 뜻입니다. 

[Rules_규칙]

목표: 주어진 격자 내에서 각 노드의 오른쪽 및 아래쪽 이웃 노드를 찾아서 출력하는 것입니다.

 

규칙:

• 노드를 포함하는 (x1, y1) 좌표를 찾아 오른쪽에 있는 가장 가까운 다음 노드의 (x2, y2) 좌표와 아래쪽에 있는 가장 가까운 다음 노드의 (x3, y3) 좌표를 출력
• 이웃이 없으면 (x2, y2) 및/또는 (x3, y3) 대신 -1 -1 좌표를 출력
• 잘못된 이웃을 제공하거나 비어있는 셀의 이웃을 계산하거나 노드의 이웃을 계산하지 않거나 동일한 노드를 두 번 계산하면 실패
• 모든 노드가 올바르게 표시되면 승리

노드 찾는 영상

[문제]

 

https://www.codingame.com/training/medium/there-is-no-spoon-episode-1

Practice Lists with the exercise "There is no Spoon - Episode 1"

 

[난이도]

[학습 개념]

 

[풀이]

먼저 2차원 좌표이기 때문에 조건반사적으로 2중 배열을 선언하고 나서 생각에 잠겼습니다.

        int width = int.Parse(Console.ReadLine()); // the number of cells on the X axis
        int height = int.Parse(Console.ReadLine()); // the number of cells on the Y axis
        for (int i = 0; i < height; i++)
        {
            string line = Console.ReadLine(); // width characters, each either 0 or .
        }

그리고 위의 초기 코드에서 그리드의 너비와 높이 그리고 열에 들어갈 문자열을 주고 있어

        int width = int.Parse(Console.ReadLine()); // 그리드의 너비를 입력받음
        int height = int.Parse(Console.ReadLine()); // 그리드의 높이를 입력받음

        // 입력받은 그리드를 2D 문자 배열로 변환함
        char[,] grid = new char[width, height];
        for (int y = 0; y < height; y++)
        {
            string line = Console.ReadLine();
            for (int x = 0; x < width; x++)
            {
                grid[x, y] = line[x];
            }
        }

2중 배열에 line의 값들을 넣어줬습니다.

이렇게 하고 또 어떻게 할까 하니까 노드가 있는 셀을 찾고 그 노드를 기준으로 오른쪽과 아래쪽의 노드를 찾으면 되겠구나 하고 생각했습니다.

그리고 이 과정을 반복하면 시간은 걸리겠지만 다 찾겠다 해서 다음의 코드를 구현했습니다.

// 모든 좌표를 돌며 각 노드의 이웃을 찾음
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                if (grid[x, y] == '0')
                {
                    int x2 = -1, y2 = -1, x3 = -1, y3 = -1;

                    // 오른쪽에 있는 이웃 찾기
                    for (int i = x + 1; i < width; i++)
                    {
                        if (grid[i, y] == '0')
                        {
                            x2 = i;
                            y2 = y;
                            break;
                        }
                    }

                    // 아래쪽에 있는 이웃 찾기
                    for (int j = y + 1; j < height; j++)
                    {
                        if (grid[x, j] == '0')
                        {
                            x3 = x;
                            y3 = j;
                            break;
                        }
                    }

                    Console.WriteLine("{0} {1} {2} {3} {4} {5}", x, y, x2, y2, x3, y3); // 이웃들의 위치를 출력함
                }
            }
        }

노드를 찾으면 일단 오른쪽과 아래쪽 노드가 없다고 가정하고 오른쪽에서 가장 가까운 노드를 찾기 위해 x+1부터 width-1까지 반복해서 찾고 찾으면 반복문을 빠져나옵니다. 아래쪽 노드 찾기도 동일하게 하고 출력하면 정답으로 인정됩니다.

[소스 코드]

 

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

class Solution
{
    static void Main(string[] args)
    {
        int width = int.Parse(Console.ReadLine()); // 그리드의 너비를 입력받음
        int height = int.Parse(Console.ReadLine()); // 그리드의 높이를 입력받음

        // 입력받은 그리드를 2D 문자 배열로 변환함
        char[,] grid = new char[width, height];
        for (int y = 0; y < height; y++)
        {
            string line = Console.ReadLine();
            for (int x = 0; x < width; x++)
            {
                grid[x, y] = line[x];
            }
        }

        // 모든 좌표를 돌며 각 노드의 이웃을 찾음
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                if (grid[x, y] == '0')
                {
                    int x2 = -1, y2 = -1, x3 = -1, y3 = -1;

                    // 오른쪽에 있는 이웃 찾기
                    for (int i = x + 1; i < width; i++)
                    {
                        if (grid[i, y] == '0')
                        {
                            x2 = i;
                            y2 = y;
                            break;
                        }
                    }

                    // 아래쪽에 있는 이웃 찾기
                    for (int j = y + 1; j < height; j++)
                    {
                        if (grid[x, j] == '0')
                        {
                            x3 = x;
                            y3 = j;
                            break;
                        }
                    }

                    Console.WriteLine("{0} {1} {2} {3} {4} {5}", x, y, x2, y2, x3, y3); // 이웃들의 위치를 출력함
                }
            }
        }
    }
}

 

[아쉬웠던 점]

반복문을 세번이나 중첩했습니다. 시간 복잡도가 O(n³)입니다.
좀 더 빠른 방법이 분명 있을 텐데 방법을 모르겠었습니다.

 

[새롭게 알게된 점]

여기서 CondinGame 사이트가 좋은 게 다른 사람들이 푼 좋은 코드를 볼 수 있다는 점입니다.

문제를 풀면 다른 사람이 공개한 코드를 볼 수 있다.

 

위의 사진에서 두 번째 분의 코드를 보면

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Don't let the machines win. You are humanity's last hope...
 **/
class Player
{
    static void Main(string[] args)
    {
        int width = int.Parse(Console.ReadLine()); // the number of cells on the X axis
        int height = int.Parse(Console.ReadLine()); // the number of cells on the Y axis
        
        List<Tuple<int, int>> nodes = new List<Tuple<int, int>>();
        for (int i = 0; i < height; i++)
        {
            string line = Console.ReadLine(); // width characters, each either 0 or .
            
            for (int j =0; j < line.Length; j++)
                if (line.ToCharArray()[j] == '0')
                    nodes.Add(Tuple.Create(j, i));
        }
        

        // Write an action using Console.WriteLine()
        // To debug: Console.Error.WriteLine("Debug messages...");
        foreach (Tuple<int, int> node in nodes)
        {
            var down = nodes.FirstOrDefault(t => t.Item1 == node.Item1 && t.Item2 > node.Item2) ?? Tuple.Create(-1, -1);
            var right = nodes.FirstOrDefault(t => t.Item1 > node.Item1 && t.Item2 == node.Item2) ?? Tuple.Create(-1, -1);
            Console.WriteLine(string.Format("{0} {1} {2} {3} {4} {5}", node.Item1, node.Item2, right.Item1, right.Item2, down.Item1, down.Item2));
        }
        
        Console.WriteLine("0 0 1 0 0 1"); // Three coordinates: a node, its right neighbor, its bottom neighbor
    }
}

시간 복잡도가 O(n²)입니다.

위의 코드를 학습하면서 새롭게 알게 된 점들이 많았습니다.

1. Tuple 클래스에 대해 처음으로 알게 되었고 찾아보면 정의와 사용법을 알게 되었습니다.
   
   
2. ToCharArray() 메서드에 대해 알게 되었습니다.
   
   
3. List를 통해 2차원 배열을 만드는 방법을 알게 되었고
   
   
4. FirstOrDefault()라는 LINQ 메서드를 알게 되었습니다. LINQ 메서드 너무 유용한데 익숙해지지가 않네요..ㅠ
   FirstOrDefault()는 LINQ 메서드 중 하나로, 컬렉션에서 조건을 만족하는 첫 번째 요소를 반환합니다. 조건을 만족하는 요소가 없을 경우 null을 반환합니다.
   

다시 첫 번째 분의 코드를 보면

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

/**
 * Don't let the machines win. You are humanity's last hope...
 **/
class Player
{
    public class Point
    {
        public int X { get; set; } = -1;
        public int Y { get; set; } = -1;
    }

    static void Main(string[] args)
    {
        var width = int.Parse(Console.ReadLine()); // the number of cells on the X axis
        var height = int.Parse(Console.ReadLine()); // the number of cells on the Y axis
        var points = new List<Point>();

        for (var y = 0; y < height; y++)
        {
            // width characters, each either 0 or .
            var newRow = Console.ReadLine().ToCharArray();
            var newPoints = newRow.Select((value, x) => value == '0' ? new Point { X = x, Y = y } : null);
            points.AddRange(newPoints.Where(p => p != null));
        }

        foreach (var point in points)
        {
            var pointToRight = points.FirstOrDefault(p => p.X > point.X && p.Y == point.Y) ?? new Point();
            var pointToBottom = points.FirstOrDefault(p => p.X == point.X && p.Y > point.Y) ?? new Point();

            // Three coordinates: a node, its right neighbor, its bottom neighbor
            Console.WriteLine($"{point.X} {point.Y} {pointToRight.X} {pointToRight.Y} {pointToBottom.X} {pointToBottom.Y}");
        }
    }
}

이분의 코드도 시간 복잡도가 O(n²)입니다.

이렇게 잘하는 사람의 코드를 학습할 수 있어 여렵지만 좋습니다.

위의 코드를 학습하면서 또 새롭게 학습한 내용이 많습니다.

1. Player.Point는 Point 클래스를 Player 클래스 내에 정의합니다. Point 클래스는 X 및 Y 좌표를 저장하는 두 개의 int형식 프로퍼티를 가지고 있습니다. X와 Y 프로퍼티는 get, set 접근자를 가지고 있으며, set 접근자는 -1로 초기화됩니다. 이는 좌표가 지정되지 않은 경우의 디폴트 값입니다.
   저는 좌표를 돌 때마다 디폴트 값으로 초기화해줬는데 이분은 더 똑똑하게 코드를 짰습니다. 허허
   
   
2. Select() 메서드의 람다식은 각 행의 문자열을 문자 단위로 순회하며, 현재 문자가 '0'인 경우, 새로운 Point 객체를 생성하고 X와 Y 프로퍼티를 현재 문자의 인덱스 x와 현재 높이 y로 설정합니다. '0'이 아닌 경우에는 null을 반환합니다.
   
   
3. points.AddRange(newPoints.Where(p => p!= null));은 newPoints 컬렉션에서 null이 아닌 요소만 points 컬렉션에 추가합니다. 이렇게 함으로써, 미로에서 '0'으로 표시된 위치만 points 컬렉션에 저장됩니다. 이 좌표들은 나중에 이웃 노드를 찾는 데 사용됩니다.
   
   
4. AddRange() 메서드를 쓴 이유도 Add() 메서드는 리스트에 요소 하나를 추가하는 역할이고
   AddRange() 메서드는 리스트에 다른 컬렉션의 모든 요소를 추가하는 역할이기 때문에 Point 클래스의 정보를 추가하기 위해 쓰였습니다.
   
   
5. p => p.X > point.X && p.Y == point.Y는 람다 함수를 나타냅니다. 이 함수는 p라는 입력 매개변수를 가지고, p.X > point.X && p.Y == point.Y라는 조건식을 연산합니다. 여기서 p는 points 리스트에 있는 각 요소를 의미하고, point는 현재 점을 나타냅니다.
   그렇기에 p.X > point.X && p.Y == point.Y 조건은 현재 점(point)보다 오른쪽에 있으며, Y축 방향으로는 같은 점을 찾기 위한 것입니다.
   
   
6. ?? 연산자는 왼쪽 피연산자가 null이면 오른쪽 피연산자를 반환합니다. 이 경우에는 FirstOrDefault가 null을 반환하는 경우를 대비해서 new Point()를 반환합니다.