백준(boj) 14500_테트로미노 (파이썬, c++)

https://www.acmicpc.net/problem/14500

풀이

---

'ㅗ' 모양만 제외하면 나머지 4개의 모양은 뒤집고 돌리고 하다 보면 상하좌우 4방향으로 이어진 dfs로 모든 경우를 찾을 수 있다. (이전 방문한 곳으로 다시 가서 무한루프만 돌지 않게 해준다면 bfs로도 구현이 가능하다. 파이썬 코드는 둘 다 첨부) 'ㅗ' 모양은 따로 처리해주는데, 구하려고 하는 곳의 상하좌우 4개를 더하고 최솟값을 빼준다. 단 이때, 주위 블럭이 3개 밖에 없을 경우는 3개를 더해주기만 한다. (모서리에 일자로 세 개 연속된 게 답일 수도 있으므로)

python3(PyPy3 제출)

#dfs 구현
from sys import*
from collections import*
input = stdin.readline
def dfs(i, j, cnt, res):
    ans=0
    check[i][j]=1
    if cnt == 4:
        return res
    for dx, dy in dd:
        nx, ny = i+dx, j+dy
        if nx<0 or ny<0 or nx>n-1 or ny>m-1 or check[nx][ny]: continue
        check[nx][ny]=1
        ans = max(ans, dfs(nx, ny, cnt+1, res+a[i][j]))
        check[nx][ny]=0
    check[i][j]=0
    return ans
def ect(i, j):
    temp=[]
    SUM=a[i][j]
    for dx, dy in dd:
        nx, ny = i+dx, j+dy
        if nx<0 or ny<0 or nx>n-1 or ny>m-1: continue
        temp.append(a[nx][ny])
    SUM = SUM + sum(temp) - min(temp) if len(temp)==4 else SUM+sum(temp)
    return SUM
​
n,m = map(int,input().split())
a=[list(map(int,input().split()))for _ in range(n)]
res=0
dd=[(-1,0),(0,1),(1,0),(0,-1)]
check=[[0]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        check[i][j]=1
        res = max(res, dfs(i,j,0,0), ect(i,j))
        check[i][j]=0
print(res)
​
#bfs 구현
from sys import*
from collections import*
input = stdin.readline
def bfs(i, j):
    ans=0
    q=deque()
    q.append((i, j, 0, 0, a[i][j], 1))
    while q:
        x, y, prevDx, prevDy, res, cnt = q.popleft()
        if cnt == 4:
            ans = max(ans, res)
            continue
        for dx, dy in dd:
            nx, ny = x+dx, y+dy
            if nx<0 or ny<0 or nx>n-1 or ny>m-1 or (prevDx == -dx and prevDy == -dy): continue
            q.append((nx, ny, dx, dy, res+a[nx][ny], cnt+1))
    return ans
def ecp(i, j):
    arr=[]
    for dx, dy in dd:
        nx, ny = i+dx, j+dy
        if nx<0 or ny<0 or nx>n-1 or ny>m-1:continue
        arr.append(a[nx][ny])
    if len(arr)==4:
        return a[i][j]+sum(arr)-min(arr)
    else:
        return a[i][j]+sum(arr)
​
dd=[(-1,0),(1,0),(0,1),(0,-1)]
n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
ans=0
for i in range(n):
    for j in range(m):
        ans = max(ans, bfs(i,j), ecp(i,j))
print(ans)

C++

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int SIZE = 501;
int check[SIZE][SIZE]={{0,}}, a[SIZE][SIZE];
int n,m;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
​
int dfs(int x, int y, int cnt, int res){
    int ans = 0;
    if(cnt == 4) return res;
    for(int i=0; i<4; i++){
        int nx, ny;
        nx = x+dx[i], ny = y+dy[i];
        if(nx<0 || ny<0 || nx>n-1 || ny>m-1 || check[nx][ny]) continue;
        check[nx][ny]=1;
        ans = max(ans, dfs(nx, ny, cnt+1, res+a[nx][ny]));
        check[nx][ny]=0;
    }
    return ans;
}
int ecp(int x, int y){
    vector<int> v;
    for(int i=0; i<4; i++){
        int nx = x+dx[i], ny = y+dy[i];
        if(nx<0 || ny<0 || nx>n-1 || ny>m-1) continue;
        v.push_back(a[nx][ny]);
    }
    int sum=0, min=1e9;
    for(int x: v) {
        sum += x;
        if(x < min) min = x;
    }
    if(v.size()==4) return a[x][y] + sum - min;
    else return a[x][y] + sum;
}
int main(){
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            scanf("%d",&a[i][j]);
    int res = 0;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++){
            check[i][j]=1;
            res = max(res, max(dfs(i, j, 0, 0), ecp(i, j)));
            check[i][j]=0;
        }
    printf("%d", res);
    return 0;
}

고찰

---

설명을 좀 더 친절하게 할 순 없겠니? (: