🍋 문제링크

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

🥝 메모

• nx = x + dx[i] *1, ny = y + dy[i] *1

  nx = x + dx[i] *2, ny = y + dy[i] *2

  nx = x + dx[i] *2, ny = y + dy[i] *2

  이런 식으로 완전탐색을 수행하면 아래의 그림과 같이 ✔️ 부분이 확인되지 않기때문에 틀림!

  

🍉 Code

제출 날짜

2021/04/23

메모리

2156 KB

시간

132 ms

#include <iostream>
#include <vector>
#include <queue>

#define my_max(a, b) (((a)>(b))?(a):(b))

int N, M, MAX;
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
std::vector<std::vector<int> > shark;
std::vector<std::vector<int> > shark2;

struct point{
    int x;
    int y;
};

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
    std::cin >> N >> M;
    shark.resize(N+1, std::vector<int>(M+1,0));
    for(int i = 0 ; i < N ; i ++){
        for (int j = 0 ; j < M ; j ++){
            std::cin >> shark[i][j];
        }
    }
}

int bfs(int x, int y){
    int nx, ny, _safe;
    point _arr;
    std::queue <int> safe;
    std::queue <point> arr;
    shark2 = shark;
    if (shark2[x][y] == 1)
        return 0;
    safe.push(0);
    point p;
    p.x = x;
    p.y = y;
    arr.push(p);
    shark2[x][y] = 2;
    while (safe.size() > 0)
    {
        _safe = safe.front();
        safe.pop();
        _arr = arr.front();
        arr.pop();
        for(int k = 0 ; k < 8 ; k++){    
            nx = _arr.x + dx[k];
            ny = _arr.y + dy[k];
            if ((0 <= nx) && (nx < N) && (0 <= ny) && (ny < M) && shark2[nx][ny] != 2){
                if (shark2[nx][ny] == 1){
                    return _safe + 1;
                }
                else{
                    point p2;
                    p2.x = nx;
                    p2.y = ny;
                    arr.push(p2);
                    safe.push(_safe+1);
                    shark2[nx][ny] = 2;
                }
            }
        }
    }
    return my_max(N, M);
}

void solve()
{
    MAX = 0;
    for (int i = 0 ; i < N ; i++)
        for (int j = 0 ; j < M ; j++)
         MAX = my_max(MAX, bfs(i, j));
}

void print_val()
{
  std::cout << MAX;
}

int main()
{
	input_faster();
	input();
	solve();
	print_val();
	return (0);
}

제출 날짜

2021/04/23

메모리

135476 KB

시간

1008 ms

import copy

N, M = map(int, input().split())
shark = []
for i in range(N):
    shark.append(list(map(int, input().split())))

dx = [-1, -1, -1, 0, 1, 1, 1, 0]
dy = [-1, 0, 1, 1, 1, 0, -1, -1]

def bfs(x, y):
    global shark, N, M
    shark2 = copy.deepcopy(shark)
    if shark2[x][y] == 1:
        return 0
    safe = [0]
    arr = [[x, y]]
    shark2[x][y] = 2
    while len(safe) > 0:
        _safe = safe[0]
        safe.remove(_safe)
        _arr = arr[0]
        arr.remove(_arr)
        for k in range(8):
            nx = _arr[0] + dx[k]
            ny = _arr[1] + dy[k]
            if (0 <= nx < N) and (0 <= ny < M) and shark2[nx][ny] != 2:
                if shark2[nx][ny] == 1:
                    return _safe + 1
                else:
                    arr.append([nx, ny])
                    safe.append(_safe+1)
                    shark2[nx][ny] = 2

    return max(N, M)

MAX = 0
for i in range(N):
    for j in range(M):
        MAX = max(MAX, bfs(i, j))

print(MAX)