Life Engineering
[BOJ 14500] 테트로미노 (C++) 본문
https://www.acmicpc.net/problem/14500
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int graph[500][500];
struct mino{
int sum;
int cnt;
int py, px;
int y,x;
};
int bfs(int y, int x, int N, int M){
int ans=0;
queue<mino> q;
q.push({graph[y][x], 1, -1, -1, y, x});
while (!q.empty()){
mino m=q.front(); q.pop();
if (m.cnt==4){
ans=max(ans, m.sum);
continue;
}
for (int i=0; i<4; i++){
int ny=m.y+dy[i];
int nx=m.x+dx[i];
if (ny<0 || nx<0 || ny>=N || nx>=M)
continue;
if (ny==m.py && nx==m.px)
continue;
q.push({m.sum+graph[ny][nx], m.cnt+1, m.y, m.x, ny, nx});
}
}
return ans;
}
int except_(int y, int x, int N, int M){
int minVal=1001; //제일 작은 값 빼준다
int cnt=0;
int ans=graph[y][x];
for (int i=0; i<4; i++){
int ny=y+dy[i];
int nx=x+dx[i];
if (ny<0 || nx<0 || ny>=N || nx>=M)
continue;
cnt++;
minVal=min(minVal, graph[ny][nx]);
ans+=graph[ny][nx];
}
if (cnt==3)
return ans;
else if (cnt==4)
return ans-minVal;
else
return 0;
}
int main(){
int N, M;
int answer=0;
cin>>N>>M;
for (int i=0; i<N; i++){
for (int j=0; j<M; j++){
cin>>graph[i][j];
}
}
for (int i=0; i<N; i++){
for (int j=0; j<M; j++){
answer=max(bfs(i,j,N,M),answer);
//exception 처리(ㅗ 모양)
answer=max(except_(i,j,N,M), answer);
}
}
cout<<answer<<"\n";
return 0;
}
이것 역시 처음에 큐를 한번만 써서 해결하려다가 자꾸 꼬여서.. 힌트를 보고 풀었다.
나는 bfs로 풀었으나 재귀 사용해서 dfs 이용해서 탐색해줘도 된다.
모양은 "테트로미노"이나 잘 살펴보면 이 모양이 서로 인접한 사각형들의 모임임을 알 수 있다. 즉 bfs 로 인접한 애들을 모두 탐색하면 된다는 뜻. 그런데 여기서 함정은 'ㅗ' 이 모양은 bfs나 dfs로 탐색 불가능하다. 이 모양 같은 경우에는 따로 빼줘서 계산해줘야 된다.
우선 모든 좌표에 대해 bfs 탐색을 돌려 가능한 모든 경우의 수를 탐색한다.
큐에는 부모 좌표도 같이 저장해서 왔던 길을 또 되돌아가는 일이 없게 한다. 즉 next 좌표와 부모 좌표가 같으면 그것은
탐색하지 않는다.
탐색한 좌표가 4개가 되면 값을 계산한다.(테트로미노니까 4개)
'ㅗ' 모양은 except_ 로 구현했다. '+' 모양이 나올 때는 여기서 인접한 좌표들 중 최소값을 갖는 애를 합에서 빼준다.
'ㅗ' 모양 나올 때는 그대로 그 합들을 리턴하면 된다. 'ㅗ' 모양은 bfs 로 탐색 불가능하기 때문에 수동으로 해줘야된다.
2가지 탐색(bfs 탐색, 'ㅗ' 탐색)을 모든 좌표에 대해 돌려주고 최대값을 구해주면 된다.
ㅗ 모양을 잘 보고 이건 bfs 탐색으로 불가능한 케이스임을 캐치하는 게 중요했다.
그리고 복잡하게 생각말고 각 좌표별로 bfs 돌리자.. 그래봤자 시간복잡도 O(M*N*4**3) 으로 충족된다.
괜히 처음에 visited 배열 여러개 만들고 그랬다.... 다시 온 길을 안되돌아 갈려면 부모 좌표를 큐에 같이 저장해서 다음 좌표가 부모 좌표와 같은지만 체크해주면 된다.
'Problem Solving' 카테고리의 다른 글
[BOJ 14890] 경사로 (C++) (0) | 2021.10.04 |
---|---|
[프로그래머스] 뉴스 클러스터링 (C++) (0) | 2021.10.02 |
[BOJ 13460] 구슬 탈출2 (C++) (0) | 2021.10.02 |
[BOJ 14503] 로봇 청소기 (C++) (0) | 2021.10.01 |
[프로그래머스] 괄호 변환 (C++) (0) | 2021.09.30 |