Excercism - Word Search : 인접노드, DFS

문제요약

좌우, 상하, 대각선 방향으로 찾고자 하는 단어가 있는지 확인하고

시작점과 끝점의 좌표를 출력하라.

 

---

난이도

Medium

---

풀이 포인트

• 방향별 탐색과 좌표

---

REVIEW

 

우선 파라미터나, 반환형에 튜플이 너무 많이 사용되어 있어서 코드 읽기가 어려웠다.

그리고 2차원 배열과 좌표 연관짓는건 늘 그려서 시각화해야 헷갈리지 않는다.

찬찬히 쪼개어 해결해 나가는 능력이 아직 부족한듯하다.

생각하다 지쳐서 첫번째 제출엔 차력으로 구현했다.. 

---

CODE

// 모범 풀이

using System;
using System.Collections.Generic;

public class WordSearch
{
    // 퍼즐을 저장할 배열
    private readonly string[] puzzles;

    // 탐색할 방향 (8방향)
    private readonly (int, int)[] directions = new []
    { (-1,-1), (0,-1), (1,-1), (1,0), (1,1), (0,1), (-1,1), (-1,0) };

    // 생성자 - grid를 받아서 puzzles 배열로 분할
    public WordSearch(string grid)
    {
        this.puzzles = grid.Split('\n');
    }

    // 단어들을 찾아서 딕셔너리로 반환
    public Dictionary<string, ((int, int), (int, int))?> Search(string[] wordsToSearchFor)
    {
        var result = new Dictionary<string, ((int, int), (int, int))?>();

        foreach (var word in wordsToSearchFor)
        {
            result[word] = FindCoordinates(word);
        }

        return result;
    }

    // 찾는 단어의 시작과 끝 좌표 출력해주는 역할
    private ((int, int), (int, int))? FindCoordinates(string word)
    {
        for (int y = 0; y < puzzles.Length; y++)
        {
            for (int x = 0; x < puzzles[y].Length; x++)
            {
                // 첫 글자 일치 확인
                if (puzzles[y][x] == word[0])
                {
                    // 방향마다 탐색
                    foreach (var direction in directions)
                    {
                        var result = MoveNCheck(word, x, y, direction);
                        if (result != null)
                        {
                            return result;
                        }
                    }
                }
            }
        }

        return null;  // 단어를 찾지 못한 경우
    }

    // 방향대로 전진하며 탐색하는 역할
    private ((int, int), (int, int))? MoveNCheck(string word, int x, int y, (int dx, int dy) direction)
    {
        var coords = new (char, int nx, int ny)[word.Length];

        // 각 문자의 좌표 계산
        for (int i = 0; i < word.Length; i++)
        {
            coords[i] = (word[i], x + i * direction.dx, y + i * direction.dy);
        }

        bool valid = true;
        foreach (var coord in coords)
        {
            // 좌표가 유효한지 확인 (인덱스가 grid의 범위 내에 있는지 체크)
            if (coord.nx < 0 || coord.nx >= puzzles[0].Length || coord.ny < 0 || coord.ny >= puzzles.Length)
            {
                valid = false;
                break;
            }

            // 문자 일치 여부 확인
            if (puzzles[coord.ny][coord.nx] != coord.Item1)
            {
                valid = false;
                break;
            }
        }

        if (!valid)
            return null;

        var end = coords[coords.Length - 1];
        return ((x + 1, y + 1), (end.nx + 1, end.ny + 1));  // 좌표는 1-based로 반환
    }
}

 

// 차력 풀이

using System;
using System.Collections.Generic;

public class WordSearch
{
    public string[] puzzles;

    public WordSearch(string grid)
    {
        this.puzzles = grid.Split('\n');
    }

    public Dictionary<string, ((int, int), (int, int))?> Search(string[] wordsToSearchFor)
    {
        var result = new Dictionary<string, ((int, int), (int, int))?>();

        foreach (string word in wordsToSearchFor)
        {
            bool found = false;
            for (int i = 0; i < puzzles.Length && !found; i++)
            {
                for (int j = 0; j < puzzles[0].Length && !found; j++)
                {
                    if (isLR(i, j, word))
                    {
                        result[word] = ((j+1, i+1), (j + word.Length, i+1));
                        found = true;
                    }
                    else if (isRL(i, j, word))
                    {
                        result[word] = ((j+1, i+1), (j - word.Length + 2, i+1));
                        found = true;
                    }
                    else if (isTopBottom(i, j, word))
                    {
                        result[word] = ((j+1, i+1), (i + word.Length, j+1));
                        found = true;
                    }
                    else if (isBottomTop(i, j, word))
                    {
                        result[word] = ((j+1, i+1), (j+1,i - word.Length + 2 ));
                        found = true;
                    }
                    else if (isD_TL_BR(i, j, word))
                    {
                        result[word] = ((j+1, i+1), (j + word.Length ,i + word.Length));
                        found = true;
                    }
                    else if (isD_BL_TR(i, j, word))
                    {
                        result[word] = ((j+1, i+1), (j + word.Length ,i - word.Length + 2));
                        found = true;
                    }
                    else if (isD_TR_BL(i, j, word))
                    {
                        result[word] = ((j+1, i+1), (j - word.Length + 2,i + word.Length));
                        found = true;
                    }
                    else if (isD_BR_TL(i, j, word))
                    {
                        result[word] = ((j+1, i+1), (j - word.Length + 2,i - word.Length + 2));
                        found = true;
                    }
                }
            }
            if (!found)
            {
                result[word] = null; // 단어를 찾지 못한 경우 null 저장
            }
        }

        return result;
    }

    public bool isLR(int i, int j, string word)
    {
        if (j + word.Length > puzzles[i].Length) return false;
        for (int a = 0; a < word.Length; a++)
        {
            if (puzzles[i][j + a] != word[a]) return false;
        }
        return true;
    }

    public bool isRL(int i, int j, string word)
    {
        if (j - word.Length + 1 < 0) return false;
        for (int a = 0; a < word.Length; a++)
        {
            if (puzzles[i][j - a] != word[a]) return false;
        }
        return true;
    }

    public bool isTopBottom(int i, int j, string word)
    {
        if (i + word.Length > puzzles.Length) return false;
        for (int a = 0; a < word.Length; a++)
        {
            if (puzzles[i + a][j] != word[a]) return false;
        }
        return true;
    }

    public bool isBottomTop(int i, int j, string word)
    {
        if (i - word.Length + 1 < 0) return false;
        for (int a = 0; a < word.Length; a++)
        {
            if (puzzles[i - a][j] != word[a]) return false;
        }
        return true;
    }

    public bool isD_TL_BR(int i, int j, string word)
    {
        if (i + word.Length > puzzles.Length || j + word.Length > puzzles[i].Length) return false;
        for (int a = 0; a < word.Length; a++)
        {
            if (puzzles[i + a][j + a] != word[a]) return false;
        }
        return true;
    }

    public bool isD_BL_TR(int i, int j, string word)
    {
        if (i - word.Length + 1 < 0 || j + word.Length > puzzles[i].Length) return false;
        for (int a = 0; a < word.Length; a++)
        {
            if (puzzles[i - a][j + a] != word[a]) return false;
        }
        return true;
    }

    public bool isD_TR_BL(int i, int j, string word)
    {
        if (i + word.Length > puzzles.Length || j - word.Length + 1 < 0) return false;
        for (int a = 0; a < word.Length; a++)
        {
            if (puzzles[i + a][j - a] != word[a]) return false;
        }
        return true;
    }

    public bool isD_BR_TL(int i, int j, string word)
    {
        if (i - word.Length + 1 < 0 || j - word.Length + 1 < 0) return false;
        for (int a = 0; a < word.Length; a++)
        {
            if (puzzles[i - a][j - a] != word[a]) return false;
        }
        return true;
    }
}