이번 문제는 비트마스킹을 활용한 BFS를 통해 해결하였다. grid를 돌며 시작 위치를 저장하고, num을 1부터 시작하여 X를 만날 때마다 해당 위치의 값을 num으로 바꿔주고 num을 1 증가시키는 방식으로 각각의 물건에 번호를 부여하였다. 그리고 방문처리 리스트를 3차원 리스트로 선언한다. visited[y좌표][x좌표][수거한물건들]로 관리된다. BFS 탐색 시에는 큐에 (y좌표, x좌표, 수거한물건들, 시간)을 넣어준다. 그리고 4방향으로 탐색을 하며 다음 좌표가 숫자이고, 수거한 물건들 & 1<<다음 좌표값이 다음 좌표값과 다르고(해당 물건을 아직 수거하지 않은 경우), visited[ny][nx][수거한 물건들 | 1<<다음 좌표값]이 False일 경우에 visited[ny][nx][수거한 물건들 | 1<<다음 좌표값]을 방문처리하고 큐에 (ny, nx, 수거한 물건들 | 1<<다음 좌표값, time+1)을 넣도록 하였다. 다음 좌표값이 숫자가 아닐 경우에는 방문처리를 확인하여 큐에 넣도록 하였다.

수거한 물건들 & 1<<다음 좌표값은 해당 물건을 수거한 경우인지 아닌지를 확인하기 위한 과정이고, 수거한 물건들 | 1<<다음 좌표값은 해당 물건을 수거한 값을 구하는 과정이다.

Code

from collections import deque
n, m = map(int, input().split())
grid = [list(str(input())) for _ in range(m)]
stuffs = []
sy, sx = 0, 0
num = 1
for i in range(m):
    for j in range(n):
        if grid[i][j] == 'S':
            sy, sx = i, j
        if grid[i][j] == 'X':
            stuffs.append((num, i, j))
            grid[i][j] = str(num)
            num += 1
visited = [[[False for _ in range(64)] for _ in range(n)] for _ in range(m)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def ready_to_go():
    q = deque()
    q.append((sy, sx, 1, 0))
    visited[sy][sx][1] = True
    while q:
        y, x, cnt, time = q.popleft()
        if grid[y][x] == 'E' and cnt == (1 << num) - 1:
            return time
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < m and 0 <= nx < n and grid[ny][nx] != '#':
                if str(grid[ny][nx]).isdigit():
                    if cnt&(1 << int(grid[ny][nx])) != int(grid[ny][nx]):
                        if not visited[ny][nx][cnt|(1 << int(grid[ny][nx]))]:
                            visited[ny][nx][cnt|(1 << int(grid[ny][nx]))] = True
                            q.append((ny, nx, cnt|(1 << int(grid[ny][nx])), time+1))
                else:
                    if not visited[ny][nx][cnt]:
                        visited[ny][nx][cnt] = True
                        q.append((ny, nx, cnt, time+1))
    return -1
print(ready_to_go())