Count Luck

Problem Link
https://www.hackerrank.com/challenges/count-luck/problem?isFullScreen=true

✅ Problem Summary

., X, M, * 로 이루어진 행렬에서 시작점인 M에서 목적지인 * 까지 이동하면서 만날 수 있는 교차점의 갯수를 세는 문제

• 상하좌우로 움직일 수 있으며, 값이 . 인 위치로만 움직일 수 있음
• M에서 * 까지는 오직 한 개의 길만 존재
• 입력된 k값과 실제로 계산한 교차로 갯수가 일치하면 Impressed, 일치하지 않으면 Oops!를 출력

---

🧮 Applied Theory & Algorithm

1. 깊이 우선 탐색(Depth-First Search)

그림출처:Wikipedia

---

📑 My Answer

• 모든 테스트 케이스 통과

def findMPosition(matrix):
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == 'M':
                return [i, j]

def checkIntersection(pos):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    res = []

    for i in range(4):
        nx, ny = pos[0] + dx[i], pos[1] + dy[i]
        if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] != 'X':
            res.append([nx, ny])
    return res

def dfs(matrix, wave_cnt, pos):
    if matrix[pos[0]][pos[1]] == '*':
        return wave_cnt

    matrix[pos[0]][pos[1]] = 'X'
    moves = checkIntersection(pos)
    if len(moves) > 1:
        wave_cnt += 1
    for nx, ny in moves:
        result = dfs(matrix, wave_cnt, pos=[nx, ny])
        if result != -1:
            return result
    return -1

def countLuck(matrix, k):
    temp_pos = findMPosition(matrix)
    wave_cnt = dfs(matrix, 0, pos=temp_pos)
    return 'Oops!' if wave_cnt != k else 'Impressed'

📌 코드 구현 설명

• M부터 *까지 한 개의 길만 존재한다는 점에서,DFS 알고리즘 활용
• 우선 findMPosition 함수로 M의 위치를 탐색
• M의 위치를 찾으면, dfs 함수를 이용해 *까지의 길을 탐색
  • 방문 위치(노드)는 X로 표시하여 다시 방문하지 못하게 함
  • 매 탐색 마다 해당 위치가 교차점에 해당하는지 확인 (checkIntersection 함수)
  • 해당 위치에서 갈 수 있는 길이 2개 이상이면 교차점으로 판별하여 교차점 갯수 + 1 을 수행
• *에 도착하면 입력 k와 실제 교차점 갯수를 비교하여 결과 출력

---