[프로그래머스] 2025 프로그래머스 코드챌린지 1차 예선 - 지게차와 크레인 - Lv.

[오늘의 문제]

https://school.programmers.co.kr/learn/courses/30/lessons/388353

프로그래머스

---

[오늘의 학습 키워드]

• BFS

---

1. 문제설명

 

requests에 해당 배열에서 제거할 문자가 들어옵니다.

requests에 들어오는 문자의 길이는 1 혹은 2가 들어오는데

 

문자의 길이가 1이 온 경우 지게차 작업을 수행하여 현재 제거 가능한 해당 문자만 찾아 배열에서 제거합니다.

문자의 길이가 2가 온 경우 크레인 작업을 수행하여 해당하는 모든 문자를 배열에서 제거합니다.

 

모든 작업이 종료 되었을 때, 배열에 남아있는 문자의 갯수를 구하는 문제입니다.

 

한가지 유의점이 있는데 

 

 

입출력 예시로 첫번째가 온 경우 입니다.

 

처음 A가 온 경우 위 문제설명의 1번 제거작업을 수행합니다.

 

2번 작업은 크레인 이므로 모든 B를 제거합니다.

 

3번 A의 경우 현재 외부에서 접촉이 가능한 A 는 배열 1,1에 위치한 A 뿐이고

 

4번 작업으로 A가 온 경우 1, 2에 위치한 A도 제거할 수 있습니다.

 

이를 유의하며 문제를 해결하여야 합니다.

---

[제한사항]

• 2 ≤ storage의 길이 = n ≤ 50
  • 2 ≤ storage[i]의 길이 = m ≤ 50
    • storage[i][j]는 위에서 부터 i + 1번째 행 j + 1번째 열에 놓인 컨테이너의 종류를 의미합니다.
    • storage[i][j]는 알파벳 대문자입니다.
•    1 ≤ requests의 길이 ≤ 100
  • 1 ≤ requests[i]의 길이 ≤ 2
  • requests[i]는 한 종류의 알파벳 대문자로 구성된 문자열입니다.
  • requests[i]의 길이가 1이면 지게차를 이용한 출고 요청을, 2이면 크레인을 이용한 출고 요청을 의미합니다.

---

2. 접근방식

BFS 작업을 수행하면 해결 가능한 문제 입니다.

 

저는 처음에 DFS 탐색을 실시하며 제거 가능한 모든 문자를 탐색하고 해당 위치에서 바깥으로 연결이 된다면 바로 문자를 제거하는 형식으로 코드를 구성하였습니다.

 

동시에 중복 탐색을 방지하기 위해 방문배열을 생성하였으나 해당 코드는 문제가 있었습니다.

1,1의 A를 제거한 경우 다음 탐색위치인 1,2를 탐색하는데 해당 위치에서 바깥으로 연결 가능한 길을 찾을 때 1, 1이 제거되며 바깥과 연결되어 1, 2 도 제거가 되었습니다.

 

따라서 반대로 생각해 보았습니다.

배열의 밖에서 부터 탐색을 실시하는데 너비 우선 탐색을 실시합니다.

그러기 위해 배열 전체에 0을 둘러싸 탐색 시작 위치를 고정해 주었습니다.

0, 0 위치에서 배열을 탐색하며 지게차가 이동 가능한 경로를 찾습니다.

이동 가능한 경로는 0으로 표시해 줄 것입니다.

 

지게차는 탐색을 위해 0으로 된 길을 이동하는데 중복 탐색을 방지하기 위해 visited 배열을 통해 방문 처리를 실시해 줄 것입니다.

 

지게차는 현재 위치에서 4방향 탐색을 실시해 request와 같은 글자를 가진 문자가 있는지 탐색해 줍니다.

 

만약 해당하는 문자가 있는 경우 해당 문자를 0으로 제거하고 다음 탐색을 실시합니다.

이때 문자를 제거하고 발생한 0은 다음 탐색위치로 넣지 않습니다.

 

만약 해당 위치를 다음 탐색 가능 위치로 넣어버리면 1, 1 과 1, 2가 같이 제거된 앞선 오류를 그대로 따라가기 때문입니다.

 

이런식으로 너비 우선 탐색을 통해 이동 가능한 경로에서 만나는 첫 문자를 모두 제거하여 줍니다.

 

크레인 작업의 경우 배열의 크기가 최대 50 x 50 이므로 전체 탐색을 통해 해당 문자를 제거해 줍니다.

 

이후 남은 문자의 갯수를 세어 주었습니다.

 

더 자세한 설명은 코드를 통해 알아보겠습니다.

 

---

3. 코드

from collections import deque

def solution(storage, requests):
    n = len(storage)
    m = len(storage[0])
    
    # 델타탐색
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    # 입력받은 storage 주변에 0 둘러주기
    arr = [[0] * (m + 2) for _ in range(n + 2)]
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            arr[i][j] = storage[i-1][j-1]

BFS 탐색을 위해 queue를 사용하고 입력을 받아줍니다.

이때 주변에 0으로 둘러싸기 위해 새로운 배열 arr을 기존의 배열보다 길이가 2씩 더 길게 생성해 줍니다.

그 후 1,1 부터 n, m 까지 값을 넣어줍니다.

# 탐색시작
    for request in requests:
        visited = [[False] * (m + 2) for _ in range(n + 2)] # 방문여부 처리할 배열
        
        # 지게차 작업
        if len(request) == 1:
            queue = deque([(0, 0)]) # 탐색 시작 위치
            visited[0][0] = True    # 시작 위치 방문 처리
            
            # 너비 우선 탐색(BFS) 실시
            while queue:
                x, y = queue.popleft()
                
                # 4방향 탐색하며 이동 가능경로 모두 찾기
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    
                    # 아직 방문하지 않았고 배열의 안쪽인 경우
                    if 0 <= nx < n+2 and 0 <= ny < m+2 and not visited[nx][ny]:
                        visited[nx][ny] = True
                        
                        # 다음 탐색 위치 찾기 0인경우 queue에 넣고 아닌 경우 0으로 변경
                        # 그러나 현재 위치를 기준으로 다음 탐색 위치는 무조건 방문 처리를 해주기에
                        # 값을 바꿔도 올바르게 동작한다.
                        
                        if arr[nx][ny] == 0:
                            queue.append((nx, ny))
                        elif arr[nx][ny] == request:
                            arr[nx][ny] = 0

입력받은 request에 따라 수행할 작업을 구분해 줍니다.

현재 입력받은 request의 길이가 1이라 지게차 작업을 수행해 줄건데 request 마다 발생하는 지게차 작업은 독립수행 되어야 합니다.

즉 배열에서 제거된 문자값을 사용하는건 동일한데 방문여부까지 받아서 사용하면 안된다는 의미입니다.

따라서 request마다 방문 여부를 확인할 visited를 생성해 주고 지게차 탐색을 실시합니다.

시작 위치는 0,0 으로 고정하고 해당 위치를 방문처리 해줍니다.

 

다음  탐색위치는 queue의 popleft를 통해 x와 y값을 받고 dx 와 dy값을 더해 nx, ny 값을 구해줍니다.

다음 탐색 위치가 배열의 범위를 벗어나지 않고 아직 방문하지 않은 경우만 탐색을 실시할건데

 

만약 다음 위치가 0으로 이동 가능한 길이라면 queue에 넣어주고 그게 아닌 찾으려는 문자라면 해당 문자를 제거하고 탐색을 종료합니다.

 

이렇게 BFS 탐색을 실시하여 문자를 제거해 줍니다.

 

        # 크레인 작업
        else:
            for i in range(1, n + 1):
                for j in range(1, m + 1):
                    if arr[i][j] == request[0]:
                        arr[i][j] = 0
    answer = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if arr[i][j] != 0:
                answer += 1
    return answer

 

이제 크레인 작업을 수행해 줍니다.

만약 request의 길이가 2 인 경우 배열에서 해당 문자를 제거해줍니다.

 

그 후 정답을 세어줍니다.

 

---

4. 결과

---

[회고]

오랜만에 코드를 푸니 DFS와 BFS가 제대로 생각나지 않았고 DFS와 방문 처리의 늪에 빠져 1시간 이상 허우적 거린 문제였습니다.

처음 작성한 코드에서 조금씩 수정하며 결과를 찾다 예제를 맞춰 실행해보니 반례가 존재하였고 계속 코드를 수정하다 결국 초기화하고 다르게 생각해 보았습니다.

 

탐색의 시작 위치를 고정하고 탐색을 실시하며 동시에 문자를 제거하는게 아니라 따로따로 탐색과 제거를 따로 시행해야겠다 생각했습니다.

 

그러다 BFS가 떠올랐고 기존의 DFS 코드를 BFS 코드로 수정하며 문제를 해결할 수 있었습니다.

 

마지막 3번 조건 때문에 애를 많이 먹어 고생한 문제 였습니다.