-
Programmers [2018 KAKAO BLIND RECRUITMENT]: [1차] 프렌즈4블록/BFSProblem Solving/Programmers 2021. 1. 3. 23:16
programmers.co.kr/learn/courses/30/lessons/17679
전형적인 좌표평면 문제이당
1️⃣블록 팝 2️⃣중력 이라는, 코딩테스트에 매우매우 자주 나오는 빈출 유형이기 때문에 반드시 여러 유형의 문제를 풀고, 코드를 외워놔야 한다
1️⃣블록 팝: 인접한 블록과 같다면 해당 블록을 팝 한다. 중요한 것은 이중 for문을 돌면서 실시간으로 pop을 해주면 안 되고, 팝 목록에 추가만 해줘야 한다
해당 그림에서 좌표가 (1,0)일 때 인접한 네 칸을 pop한다면, 두 빨간 박스에 겹쳐 있는 오른쪽 아래 라이언도 없어지기 때문에 아래에 있는 박스는 제대로 pop할 수 없다
따라서 check배열을 선언해줘서, pop할 좌표들을 전부 체크해준 뒤 한꺼번에 pop한다
2️⃣중력: 해당 좌표들이 pop된 뒤, 위에 있는 블록들을 밑으로 전부 내려주는 작업이다. 이는 큐를 이용해서 의외로 간단하게 구현할 수 있다.
바로 모든 열에 대해 가장 아래 행부터 제일 위의 행까지 존재하는 블록을 모두 큐에 담은 뒤, 다시 아래부터 위의 순서로 체크하면서 큐에 있는 모든 원소를 빼주면 된다.
예를 들어 2열에서는 아래에서부터 (무지, 튜브, -, -, -, 튜브) 현재 이런 상태이다. 그러면 아래에서부터 큐에 담아 큐에는 (무지, 튜브, 튜브)가 담겨져있다. 다시 아래에서부터 순서대로 pop하면서 담아주면 (무지, 튜브, 튜브, -, -, -)가 된다.
이런 방식으로 중력 처리도 간단하게 구현할 수 있다.
모든 턴 마다 블록팝 - 중력을 계속 적용시켜 주면서, 블록팝이 일어나지 않을 때 까지 반복하면 끝 !
#include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> using namespace std; string map[31]; bool check[31][31]; int dx[] = { 1,0,1,0 }, dy[] = { 1,1,0,0 }; int solution(int n, int m, vector<string> board) { int answer = 0; while (1) { bool B = true; memset(check, 0, sizeof(check)); for (int i = 0; i < n - 1; i++) for (int j = 0; j < m - 1; j++) { char c = board[i][j]; if (c=='0')continue; bool b = true; for (int k = 0; k < 3; k++) if (board[i + dy[k]][j + dx[k]] != board[i][j]) b = false; if (b) { for (int k = 0; k < 4; k++)check[i + dy[k]][j + dx[k]] = 1; B = 0; } } for (int j = 0; j < m; j++) { queue<char> q; for (int i = n - 1; i >= 0; i--) { if (!check[i][j])q.push(board[i][j]); else answer++; board[i][j] = '0'; } for (int i = n - 1; i >= 0; i--) { if (q.empty())break; board[i][j] = q.front(); q.pop(); } } if (B)break; } return answer; }
'Problem Solving > Programmers' 카테고리의 다른 글
[Programmers] 2018 KAKAO BLIND RECRUITMENT[1차] 뉴스 클러스터링 (0) 2021.02.12 [Programmers] 2018 KAKAO BLIND RECRUITMENT: [1차] 다트 게임 (3) 2021.02.05 Programmers [2019 카카오 개발자 겨울 인턴십]: 튜플 (0) 2021.01.02 Programmers [2018 KAKAO BLIND RECRUITMENT]: [1차] 비밀지도 (0) 2021.01.02 Programmers [2017 카카오코드 예선]: 카카오프렌즈 컬러링북 (0) 2020.12.31