n x n 크기의 행렬이 주어졌을 때, A[i][j] = 0인 원소를 찾아 해당 인덱스 (i, j) 사이의 차이가 가장 큰 값을 계산하는 것이 이번 문제의 목표입니다. 즉, 행렬에 포함된 0의 위치를 모두 확인한 뒤, 각 위치에서 행 인덱스 i와 열 인덱스 j의 차이(절댓값) 중 최댓값을 구하면 됩니다. 단, 이 문제에서는 행렬에 반드시 하나 이상의 0이 존재한다고 가정합니다.
문제 예시
입력
int matrix[][] = {
{0, 1, 1},
{0, 0, 0},
{4, 5, 1}}출력 − 주어진 행렬에서 A[i][j] = 0인 인덱스 (i, j)의 최대 차이는 다음과 같습니다.
설명 − 이 행렬에는 matrix[0][0], matrix[1][0], matrix[1][1], matrix[1][2] 위치에 0이 있습니다. 이 중 인덱스 차이가 가장 큰 위치는 matrix[1][0]으로, |1 − 0| = 1이므로 최대 차이는 1입니다.
입력
int matrix[][] = {
{0, 1, 1},
{0, 2, 9},
{4, 0, 1}}출력 − 주어진 행렬에서 A[i][j] = 0인 인덱스 (i, j)의 최대 차이는 다음과 같습니다.
설명 − 이 행렬에는 matrix[0][0], matrix[1][0], matrix[2][1] 위치에 0이 있습니다. 각 위치의 인덱스 차이를 계산해 보면 |0−0| = 0, |1−0| = 1, |2−1| = 1이므로 최대 차이는 1입니다.
알고리즘 접근 방법
행렬을 입력받습니다. 이때 행렬에는 최소한 하나 이상의 0이 존재해야 합니다.
행(row)과 열(column)의 최대 크기를 정의합니다. 여기서는 n x n 크기를 사용합니다.
최대 차이 값을 저장할 임시 변수를 선언하고 0으로 초기화합니다.
행 크기만큼 바깥쪽 For 루프를 시작합니다.
루프 내부에서 열 크기만큼 안쪽 For 루프를 시작합니다.
matrix[i][j] == 0인지 검사합니다.
조건이 참이라면, 현재까지의 최댓값과 |i − j|를 비교하여 더 큰 값으로 갱신합니다.
모든 탐색이 끝나면 최댓값을 반환합니다.
결과를 출력합니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
#define row 3
#define col 3
// 최대 차이를 구하는 함수
int maximum(int matrix[row][col]){
int max_val = 0;
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (matrix[i][j] == 0){
max_val = max(max_val, abs(i - j));
}
}
}
return max_val;
}
int main(){
int matrix[row][col] = {
{ 1, 2, 0},
{ 0, 4, 0},
{ 0, 1, 0}};
cout<<"A[i][j] = 0인 인덱스의 최대 차이: "<<maximum(matrix);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
A[i][j] = 0인 인덱스의 최대 차이: 2
예제 행렬에서 0의 위치는 matrix[0][2], matrix[1][0], matrix[1][2], matrix[2][0], matrix[2][2]입니다. 각 위치의 인덱스 차이는 |0−2| = 2, |1−0| = 1, |1−2| = 1, |2−0| = 2, |2−2| = 0이므로, 최대 차이는 2가 됩니다.