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 |