[프로그래머스] 지게차와 크레인

2025. 5. 27. 18:38·알고리즘
728x90
반응형

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

 

프로그래머스

SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

문제유형

  • BFS

 

문제 난이도

  • Lev2

 

문제 분석

주어진 요청 requests 에 대하여 문자열이 1개일 땐 지게차, 같은 문자열 2개일 때는 크레인을 사용하여, 동일한 문자열에 대해 컨테이너를 제거하고 남은 컨테이너 개수를 반환하는 문제이다.

요청에 대해 같은 문자열들을 처리하는 것이기 때문에 현재 문자열이 지게차를 사용하여 꺼낼 수 있는 경우, 바로 방문처리를 하면 안된다. 왜냐면 근접한 문자열중에 자신과 동일한 문자열인 경우, 해당 문자열도 해당 경로로 가게 되면 꺼낼 수 있는 경로가 될 수 있기 때문이다. -> 이 부분만 놓치지 않으면 쉽게 풀린다.

문제 자체는 어렵지 않고, BFS라는 것을 생각하기 쉽다. 방문처리에만 유의해서 문제를 풀어주면 된다.

문제 풀이 과정
1. 지게차 사용 여부 : BFS -> visited를 통해서만 이동가능하게 해서 양쪽이 벽인지 확인
2. 크레인 사용 여부 : requests에서 같은 문자열이 두 번 반복된 경우, 해당하는 모든 문자열은 방문 처리한다.

 

 

전체 코드

import java.io.*;
import java.util.*;

class Solution {
    static class Node {
        int x, y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    public int solution(String[] storage, String[] requests) {
        int N = storage.length;
        int M = storage[0].length();
        
        boolean[][] visited = new boolean[N][M];
        List<Node>[] nodes = new List[26];
        
        for(int i = 0; i < 26; i++) nodes[i] = new ArrayList<>();
        
        for(int i = 0; i < N; i++) {
            String str = storage[i];
            for(int j = 0; j < M; j++) {
                nodes[str.charAt(j) - 'A'].add(new Node(i, j));
            }
        }
        
        int res = N * M;
        for(int i = 0; i < requests.length; i++) {
            
            res -= solve(requests[i], nodes, visited, N, M);
            
        }
        
        return res;    
    }
    
    static int solve(String str, List<Node>[] nodes, boolean[][] visited, int N, int M) {
        
        int cnt = 0;
        char target = str.charAt(0);
        
        if(nodes[target - 'A'].size() == 0) return cnt;
        
        ArrayDeque<int[]> q;
        
        if(str.length() > 1) {
            
            for(Node node : nodes[target - 'A']) {
                if(visited[node.x][node.y]) continue;
                
                visited[node.x][node.y] = true;
                cnt++;
            }
            
            
        } else {
            
            List<Node> succ = new ArrayList<>();
            for(Node node : nodes[target - 'A']) {
                boolean[][] v = new boolean[N][M];
                
                if(visited[node.x][node.y]) continue;
                
                q = new ArrayDeque<>();
                 
                q.offer(new int[]{node.x, node.y});
                v[node.x][node.y] = true;
                
                while(!q.isEmpty()) {
                    
                    int[] p = q.poll();
                    
                    if(p[0] == 0 || p[0] == N - 1 || p[1] == 0 || p[1] == M - 1) {
                        succ.add(new Node(node.x, node.y));
                        cnt++;
                        break;
                    }
                    
                    for(int d = 0; d < 4; d++) {
                        int nx = p[0] + dx[d];
                        int ny = p[1] + dy[d];
                        
                        if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                        if(!visited[nx][ny] || v[nx][ny]) continue;
                        
                        q.offer(new int[]{nx, ny});
                        v[nx][ny] = true;
                    }
                }
            }
            
            for(Node node : succ) {
                visited[node.x][node.y] = true;
            }
        }
        
        return cnt;
    }
}
728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

[PCCP 기출 1번] 동영상 재생기  (0) 2025.05.29
역행렬 계산  (0) 2025.05.28
[프로그래머스] 홀짝트리  (0) 2025.05.26
[프로그래머스] 택배 상자 꺼내기  (0) 2025.05.26
[프로그래머스] 봉인된 주문  (1) 2025.05.25
'알고리즘' 카테고리의 다른 글
  • [PCCP 기출 1번] 동영상 재생기
  • 역행렬 계산
  • [프로그래머스] 홀짝트리
  • [프로그래머스] 택배 상자 꺼내기
moongi
moongi
프로그래밍 관련 공부를 정리하는 블로그
  • moongi
    By_Me
    moongi
  • 전체
    오늘
    어제
    • 공부 (81) N
      • 알고리즘 (47) N
        • 기업별 유사 문제 (2)
        • Sudo Code (5) N
        • 예외처리 (1)
        • SQL (9)
      • spring boot (6)
        • jpa (0)
        • querydsl (0)
        • MVC pattern (0)
        • setting (2)
      • 취준 (3)
      • CS (8)
        • 디자인패턴 (1)
        • 데이터베이스 (4)
        • 네트워크 (3)
        • 운영체제 (0)
  • 인기 글

  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.3
moongi
[프로그래머스] 지게차와 크레인
상단으로

티스토리툴바