[백준 1915] 가장 큰 정사각형 [C]
풀이 dp[i][j]를 기준으로, dp[i][j-1], dp[i-1][j-1], dp[i-1][j]가 모두 0이 아닌 정수일 때, 이들의 최솟값에 1을 더한 값이 dp[i][j]를 기준으로 만들어지는 정사각형의 한 변의 길이이다. 가장 큰 dp[i][j]값을 max에 담아, max의 제곱을 출력해주면 된다. 소스코드 #include int dp[1001][1001]; int min(int a, int b, int c){ if (a < b && a < c) return a; return b < c ? b : c; } int main(){ int n, m; scanf("%d %d", &n, &m); for (int i = 1; i
2021. 8. 16.
[백준 2234] 성곽 [C]
풀이 1과, 2의 답은 방 마다 bfs를 사용해 탐색하면 쉽게 구할 수 있다. 3의 답은 방의 각 칸에서 모든 방향으로 벽을 부셔보고 bfs를 사용해 탐색하면 되는데, 매번 방문한 장소를 초기화해주고, 벽을 뚫었다가 탐색이 끝나면 다시 막아주어야 한다. 방향의 순서는 문제에 주어진대로 bit값의 shift연산과 관련이 있으므로 서, 북, 동, 남 순서대로 탐색했다. 소스코드 #include #include #include #define MAX 50 int n, m, graph[MAX][MAX], rear; bool visited[MAX][MAX]; typedef struct{ int x, y; }Point; Point queue[MAX*MAX], d[4] = {{0,-1}, {-1,0}, {0,1}, {..
2021. 8. 14.
