Awesome

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl&

코드는 

https://github.com/ChangmoKang/problem_solving/blob/master/SWEA/2383.py#L74

이 분 코드를 참고했음.

1. 사람이 계단을 선택한다고 생각하지말고, 사람은 여러 명, 계단은 항상 2개이므로 계단이 사람을 선택한다고 생각한다. -> DFS가 됨

2. 계단이라고 해서 큐처럼 진짜 한 칸씩 땡겨오려고 하지 말고, 0이 되면 그 자리에 대기자를 넣는다고 생각을 하자. 

3. 사람들을 어떻게 구별하나 고민하지 말고, 여기서 필요한 정보는 각 사람~계단까지의 거리 뿐임을 기억하자. 중복되도 상관없다. 리스트에 거리만 계산해서 넣으면 끝이다. 

4. 괜히 괜히 괜히 엄청나게 복잡하고 어려운 것 같으면 뭔가 이상하다는 뜻이다. 더 쉬울만한 다른 방법을 생각해보자.

import sys


def init():
    for i in range(n):
        for j in range(n):
            if board[i][j] == 1:
                people.append([i, j])
            elif board[i][j] != 0:  # 1도 아니고 0도 아니면 계단
                stair.append([i, j, board[i][j]])


def calc_distance(pdx, sdx):
    return abs(people[pdx][0] - stair[sdx][0]) + \
            abs(people[pdx][1] - stair[sdx][1])


def start(count, choice):
    global min_time
    if count == people_num:
        wait = [[], []]
        on_stair = [[0, 0, 0], [0, 0, 0]]

        for pdx in range(people_num):  # pdx = people index
            wait[choice[pdx]].append(calc_distance(pdx, choice[pdx]))  # 거리를 대기자 리스트에 넣는다

        wait[0].sort()
        wait[1].sort()

        # 계단1,2 합쳐서 가장 먼저 도착하는 사람을 시작 시간(t)으로 놓는다.
        if wait[0] and wait[1]:
            t = min(wait[0][0], wait[1][0])
        elif wait[0] and not wait[1]:
            t = wait[0][0]
        else:
            t = wait[1][0]

        while wait[0] or wait[1]:  # 대기자가 있을 때까지 반복
            for sdx in range(2):  # sdx = stair index
                for floor in range(3):  # 매번 각 계단의 *세 자리*를 살펴서 
                    if on_stair[sdx][floor] > 0:  # 계단에 누가 있으면
                        on_stair[sdx][floor] -= 1  # 한 층 내려오게 하고
                    if on_stair[sdx][floor] == 0:  # 0이 되면 (=빈 자리가 생김)
                        if wait[sdx] and wait[sdx][0] < t:  # 해당 계단에 대기자가 있고 & 도착할 시간이 지났으면
                            on_stair[sdx][floor] = stair[sdx][H]  # 해당 계단의 높이를 리스트에 넣는다
                            wait[sdx].pop(0)
            t += 1

        t += max(max(on_stair[0]), max(on_stair[1])) - 1
        min_time = min(t, min_time)
        return
    
    else:  # DFS로 순열 찾기 (count == 사람숫자 될 때마다 본격적인 시뮬레이션 시작)
        for i in range(2):
            start(count+1, choice + [i])


if __name__ == '__main__':
    H = 2
    input = sys.stdin.readline
    T = int(input())
    for t in range(T):
        n = int(input())
        min_time = 9999
        board = [list(map(int, input().split())) for _ in range(n)]
        people, stair = [], []
        init()
        people_num = len(people)

        start(0, [])
        print("#{}".format(t+1), min_time)

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

import sys
import collections


def Print(lst):
    for i in lst:
        for j in i:
            print(j, end=' ')
        print("")
    print("")


def bfs(i, j):
    visited = [[0 for _ in range(m)] for _ in range(n)]
    x = [0, 0, 1, -1]
    y = [1, -1, 0, 0]

    queue = collections.deque([[i, j, 1]])
    visited[i][j] = 1
    while queue:
        r, c, depth = queue.popleft()
        for dir in range(4):
            nR = r + x[dir]
            nC = c + y[dir]
            if 0 <= nR < n and 0 <= nC < m:
                if nR == n-1 and nC == m-1:
                    return depth+1
                if board[nR][nC] == 1 and not visited[nR][nC]:
                    visited[nR][nC] = 1
                    queue.append([nR, nC, depth+1])

        # Print(visited)


if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    board = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        tmp = sys.stdin.readline()[:-1]
        for j in range(m):
            board[i][j] = int(tmp[j])

    #Print(board)
    print(bfs(0, 0))

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

https://yabmoons.tistory.com/49

해설은 이 블로그를 참고했다. 

별다른 알고리즘이 사용되지 않지만, 쉽지는 않은 문제이다.

경계값 등 변수값을 정해줄 때 사람 헷갈리게 하는 점이 많기 때문이다...

파이썬으로 이 문제를 풀 때 유의해야 하는 점은 파이썬의 for문은 다른 언어와 다르다는 점이다.

c에서는 for (int i=0; i<n; i++) 하고 for문 내에서 i를 증가시킬 수 있지만,

python에서의 for i in range(n)은 for문 내에서 i 값을 변경시켜도 다음 반복 시 원래 값으로 돌아온다는 것.

이 문제에 적용해보면 다음과 같다. 여기서 한 번 경사로를 지은 곳은 다시 살필 필요가 없다. 쩜프쩜프! 

예를 들어 어떤 행이 [ 3 2 2 1 ]이고 경사로 길이가 2였을 때, 첫 번째 주인공은 3이다.

자, 그러면 2 2 위에 경사로가 지어질 것이고.

그 다음 반복문의 주인공이 되야 하는 것은 첫번째 2를 건너뛰고 바로 두 번째 2 가 된다.

왜냐하면 한 곳 위에 두 개의 경사로가 지어질 수 없다고 문제에 나와있기 때문이다.

(*주의: 바로 1로 가면 안 된다. 이게 이 문제의 헷갈리는 점인데...두번째 2 다음에 1이 나오므로 여기에도 경사로를 지어줘야 하기 때문이다!)

아무튼 그래서 반복문 내에서 다음 주인공 원소를 만들기 위해 점프 점프 할 필요가 있고, 그래서 while문을 썼다.

결론.

이 시뮬레이션 문제는, 

첫째는 평평한 땅을 지날 때 카운트를 증가시켜준다는 것,

두번째는 경계값이나 각종 값 정해줄 때 신경써야 하는 것

이게 핵심인거같다.

import sys


def make_road(board):
    total_road = 0
    for col in range(n):
        can_be_road = True
        flat_num = 1

        row = 0
        while row < n-1:  # 반복문 내에서 row 값을 변경시킬 것이므로 for 대신 while을 쓴다.
            if board[row][col] == board[row+1][col]:  # 같은 값을 유지할 때
                flat_num += 1
                row += 1
            elif board[row][col] + 1 == board[row+1][col]:  # 높은 길을 만났을 때
                if flat_num >= l:  # 경사로 지을 수 있음
                    flat_num = 1  # 초기화
                    row += 1
                else:
                    can_be_road = False # 경사로를 한번 놓을 수 없으면 그 길은 끝
                    break
            elif board[row][col] - 1 == board[row+1][col]:  # 낮은 길을 만났을 때
                standard = board[row+1][col]
                for i in range(l):
                    if row+1+i >= n or standard != board[row+1+i][col]:  # 경사로 범위를 넘어서거나 차이가 1 이상일 때
                        can_be_road = False
                        break
                if can_be_road:
                    flat_num = 0
                    row += l
                else:
                    break
            else:
                can_be_road = False
                break
        if can_be_road:
            total_road += 1

    return total_road


if __name__ == '__main__':
    n, l = map(int, sys.stdin.readline().split())
    board_origin = []
    for _ in range(n):
        board_origin.append(list(map(int, sys.stdin.readline().split())))

    board2_origin = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            board2_origin[i][j] = board_origin[j][i]
    # 세로 길
    print(make_road(board_origin)+make_road(board2_origin))

https://programmers.co.kr/learn/courses/30/lessons/42583?language=python3

다리를 큐로 생각하고 푸는 문제이다.

트럭은 1초에 1씩 이동한다고 했는데, 이것을 실제로 지나가는 것처럼 하나하나 원소를 밀면 (다리 길이 X 트럭의 갯수)만큼의 시간이 걸려서 오래 걸리므로 간단하게 큐에서 맨 앞을 빼고 맨 뒤에 0을 추가하는 방식으로 트럭을 밀어주었다. 이렇게 하면 (트럭의 갯수)만큼의 시간이 걸리게 된다. (deque를 쓸 때의 이야기임!!)

그리고 조건에 맞으면 다리 맨 뒤에 추가한 0의 자리에 대기열에 있던 새로운 트럭을 넣도록 했다.

반복문은 대기열에 트럭이 남아있을 동안 진행되므로, 마지막 트럭이 다리에 들어선 순간 끝나게 된다. 마지막 트럭까지 다리를 모두 건넜을 때의 시간을 계산해야 하므로 결과값에 다리 길이를 추가해서 리턴하도록 했다. 

from collections import deque


def solution(bridge_length, weight, truck_weights):
    waiting = deque(truck_weights)
    bridge = deque([0 for _ in range(bridge_length)])  # queue
    answer = 0
    total = 0

    while waiting:
        total -= bridge.popleft()
        bridge.append(0)

        if total + waiting[0] <= weight:
            new_truck = waiting.popleft()
            total += new_truck
            bridge[-1] = new_truck

        #print(bridge)
        answer += 1

    answer += bridge_length
    return answer


#print(solution(2, 10, [7, 4, 5, 6]))
#print(solution(100, 100, [10]))
#print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]))

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
	int n, m;
	scanf("%d %d\n", &n, &m);
	int arr[n];

	for (int i=0; i<n; i++) {
		scanf("%d", &arr[i]);
	}

	int start = 0, end = 0, sum = 0, count = 0;

	/*
	while (start < n) {
		if (sum >= m) {
			sum -= arr[start];
			start ++;
		}
		else if (end == n) {
			break; // 이미 end가 n까지 왔다는 것은 sum이 작다는 것
		}
		else {
			sum += arr[end];
			end ++;  // end가 가리키는 부분은 포함 안 함
		}
		if (sum == m)
			count ++;
	}
	*/

	while (start < n) {
		if (sum == m)
			count ++;
		if (sum >= m) {
			sum -= arr[start];
			start ++;
		}
		else if (end > n) {
			break;
		}
		else {
			end ++;
			sum += arr[end-1];
		}
	}

	printf("%d\n", count);
	return 0;
}

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

4개의 방향을 중복 순열로 가능한 가짓수를 모두 뽑아서(4^5) 각각 이동을 시키는 방법(n^2)으로 풀었다. 

BFS,DFS로 푸는 방법도 있던데 이 방법은 완전탐색에 가까운 것 같다.

import sys
import collections
from copy import deepcopy
WEST, EAST, NORTH, SOUTH = 1, 2, 3, 4


def Print(lst):
    for i in lst:
        for j in i:
            print(j, end=" ")
        print("")
    print("")


def move_north(board):
    queue = collections.deque()
    joinable = [[True for _ in range(n)] for _ in range(n)]  # 한번 합쳐진 블록은 False로 표시
    
    # 작업할 큐를 만듦
    for row in range(n):
        for col in range(n):
            if board[row][col] != 0:  # 0이 아니면 추가
                queue.append([row, col])
            else:  # 0이면 0이 아닌 값을 땡겨와서 추가
                for sub_row in range(row+1, n):
                    if board[sub_row][col] != 0:
                        board[row][col] = board[sub_row][col]
                        board[sub_row][col] = 0
                        queue.append([row, col])
                        break

    while queue:
        row, col = queue.popleft()
        if 0 <= row + 1 < n:
            if board[row][col] == 0 and board[row+1][col] != 0:  # 처음에는 0이 아니었지만 합쳐지면서 0이 된 경우
                board[row][col] = board[row+1][col]  # row+1을 땡겨온다. joinable도 땡겨옴
                board[row+1][col] = 0
                joinable[row][col] = joinable[row+1][col]
                joinable[row+1][col] = True
                if joinable[row][col]:
                    queue.append([row, col])
            elif board[row][col] == board[row+1][col]:  # 합침
                board[row][col] = board[row][col]*2
                board[row+1][col] = 0
                joinable[row][col] = False


def move_south(board):
    queue = collections.deque()
    joinable = [[True for _ in range(n)] for _ in range(n)]
    for row in reversed(range(0, n)):
        for col in range(0, n):
            if board[row][col] != 0:
                queue.append([row, col])
            else:
                for sub_row in reversed(range(0, row)):
                    if board[sub_row][col] != 0:
                        board[row][col] = board[sub_row][col]
                        board[sub_row][col] = 0
                        queue.append([row, col])
                        break

    while queue:
        row, col = queue.popleft()
        if 0 <= row - 1 < n:
            if board[row][col] == 0 and board[row-1][col] != 0:  # 처음에는 0이 아니었지만 합쳐지면서 0이 된 경우
                board[row][col] = board[row-1][col]
                board[row-1][col] = 0
                joinable[row][col] = joinable[row-1][col]
                joinable[row-1][col] = True
                if joinable[row][col]:
                    queue.append([row, col])
            elif board[row][col] == board[row-1][col]:
                board[row][col] = board[row][col]*2
                board[row-1][col] = 0
                joinable[row][col] = False


def move_east(board):
    queue = collections.deque()
    joinable = [[True for _ in range(n)] for _ in range(n)]
    for row in range(n):
        for col in reversed(range(0, n)):
            if board[row][col] != 0:
                queue.append([row, col])  # board[row][col][1] = True
            else:  # 값이 0이면 땡겨오고나서 큐에 추가
                for sub_col in reversed(range(0, col)):
                    if board[row][sub_col] != 0:
                        board[row][col] = board[row][sub_col]
                        board[row][sub_col] = 0
                        queue.append([row, col])
                        break

    while queue:
        row, col = queue.popleft()
        if 0 <= col-1 < n:
            if board[row][col] == 0 and board[row][col-1] != 0:  # 처음에는 0이 아니었지만 합쳐지면서 0이 된 경우
                board[row][col] = board[row][col-1]
                board[row][col-1] = 0
                joinable[row][col] = joinable[row][col-1]
                joinable[row][col-1] = True
                queue.append([row, col])
            elif board[row][col] == board[row][col-1]:
                board[row][col] = board[row][col]*2
                board[row][col-1] = 0
                joinable[row][col] = False
                joinable[row][col-1] = True


def move_west(board):
    queue = collections.deque()
    joinable = [[True for _ in range(n)] for _ in range(n)]  # 한 번 합쳐진 블록은 False로 표시

    # 작업할 큐를 만듦
    for row in range(n):
        for col in range(n):
            if board[row][col] != 0:  # 0이 아닌 값만 큐에 추가
                queue.append([row, col])
            else:  # 값이 0이면 0이 아닌 것을 뒤에서 땡겨와서 그 값을 큐에 추가
                for sub_col in range(col+1, n):
                    if board[row][sub_col] != 0:
                        board[row][col] = board[row][sub_col]
                        board[row][sub_col] = 0
                        queue.append([row, col])
                        break

    while queue:
        row, col = queue.popleft()
        if 0 <= col+1 < n:
            if board[row][col] == 0 and board[row][col+1] != 0:  # 처음에는 0이 아니었지만 합쳐지면서 0이 된 경우
                board[row][col] = board[row][col+1]
                board[row][col+1] = 0
                joinable[row][col] = joinable[row][col+1]
                joinable[row][col+1] = True
                if joinable[row][col]:
                    queue.append([row, col])
            elif board[row][col] == board[row][col+1]:
                board[row][col] = board[row][col]*2
                board[row][col+1] = 0
                joinable[row][col] = False
                joinable[row][col+1] = True


###
# 중복 순열에 뽑힌 방향 순서대로 보드를 이동시키는 함수
###
def move(directions):
    global maxValue
    board = deepcopy(board_origin)  # 원본 보드가 변경되면 안되므로 deepcopy 필요

    for way in directions:
        if way == WEST:
            move_west(board)
        elif way == EAST:
            move_east(board)
        elif way == NORTH:
            move_north(board)
        elif way == SOUTH:
            move_south(board)

    # 최댓값 비교
    for line in board:
        maxValue = max(maxValue, max(line))


###
# 동서남북을 중복을 허용하면서 재귀적으로 5가지를 뽑은 후
# count가 5가 되면 그 방향대로 이동을 시작시키는 함수
###
def get_permutation_directions(count, selected):
    if count == 5:
        move(selected)
        return

    for way in [WEST, EAST, NORTH, SOUTH]:
        selected.append(way)
        get_permutation_directions(count+1, selected)
        selected.pop()


if __name__ == '__main__':
    maxValue = 0
    n = int(sys.stdin.readline())

    board_origin = []
    for _ in range(n):
        board_origin.append(list(map(int, sys.stdin.readline().split())))

    get_permutation_directions(0, [])

    print(maxValue)

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

0. 이것 때문에 엄청 헤맸다!! 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다. 를 주의하자. 나는 이 말을 처음에 '동서남북 등으로 기울이는 행동, 즉 이 게임을 그만두는 것은 구슬이 움직이지 않을 때까지(하지만 지금생각해보니 구슬이 움직이지 않을리가 없지 않은가...)'로 이해했는데, 그게 아니라 '구슬이 한번 이동하기 시작했으면 움직이지 않을 때까지 계속 이동한다'로 이해해야 한다.

1. 실제 게임하는 것처럼 살살 움직이면 중간에도 다른 방향(밑으로라던지...)으로 빠질 수 있다고 생각한게 잘못이었다. 하지만 이 게임에서 중력은 없다.

2. 방문 체크는 RED와 BLUE 따로 해 주는 것이 아니라 '동시에' 해야 한다. 빨간 공과 파란 공 둘다 방문했던 지점이어야만 한번 갔던 지점이라고 인식하고 가지 말아야 한다. 그래서 4차원 배열을 사용했다. 처음에는 4차원 배열이 직관적이지 않은 것 같아서 RED와 BLUE 각각의 2차원 배열로 체크했는데, 2차원 배열 2개와 4차원 배열 1개는 엄연히 다른 것이었다. 2차원 배열 두 개를 사용하면 독립 사건이 되는데, 4차원 배열 1개를 사용하면 조건부 확률이 된다고 해야 할까..

예를 들어 어떤 시점에서 red = [1, 1], blue = [2, 2] 였고, 그 다음에는 red = [3, 3], blue = [4, 4] 이었다고 해보자. 만약 이것을 4차원 배열로 방문 체크를 하면 visit[1][1][2][2] = 1, visit[3][3][4][4] = 1 일 것이다.

하지만 이것을 2차원 배열로 각각 체크를 하면

visit_red[1][1] = 1, visit_blue[2][2] = 1, visit_red[3][3] = 1, visit_blue[4][4] =1 이 되며 이것을 다시 4차원 배열로 바꿔보면

visit[1][1][2][2] = 1

visit[3][3][4][4] = 1

visit[1][1][4][4] = 1  <= 방문하지 않았는데

visit[3][3][2][2] = 1  <= 방문 체크가 되어버림

로 네 가지나 나오게 되어 버리며 이로 인해 방문하지 않은 지점도 방문했다고 인식하고 가지 않게 된다.

2. 방문 체크는 여느 bfs와 마찬가지로 '큐에 넣을 때' 해야 한다. 이 말은 구슬이 한 번 쭉 이동하고 난 후 멈춰선 지점이 큐에 들어간다는 뜻이 된다. 이동하는 과정에서 모든 칸이 방문 체크가 되어 버리면 안 된다. 이리저리 움직이다보면 이전에 갔던 길을 또 갈 수는 있다. 또한 move 함수 자체는 이동을 '해 보는' 함수이므로, 이동을 '해 보는' 도중에 방문 체크를 해서도 안 된다. 이동하고 나니 RED와 BLUE가 같은 곳에 있어서 이동해줘야 하는 경우였을 수도 있기 때문이다. 아니면 BLUE가 구멍에 빠졌을 수도 있고...일단 이동을 해보고 유효한 움직임이고 도착 지점이 방문한 적이 없는 지점이면 그 때 이것을 유효한 움직임이었다고 인정하고 그 다음 이동을 위해서 큐에 넣는 것이다.

3. 기울임 횟수(tilt_count) 는 큐에 넣어서 기록해야 한다. 그래야 한 번 while 문을 돌면서 동서남북으로 이동할 때 같은 tilt_count를 가지고 큐에 추가될 수 있다. while문이든 for문이든 반복문 아래에 직접 tilt_count를 세면 안 된다. 

import sys
import collections


def move(x, y, dx, dy):
    count = 0
    while board[x+dx][y+dy] != '#' and board[x][y] != 'O':
        x += dx
        y += dy
        count += 1
    return x, y, count


def bfs():
    queue = collections.deque()
    queue.append(red_first+blue_first+[1])
    visited[red_first[0]][red_first[1]][blue_first[0]][blue_first[1]] = 1
    x = [1, -1, 0, 0]
    y = [0, 0, 1, -1]

    while queue:
        rx, ry, bx, by, tilt_count = queue.popleft()

        if tilt_count > 10:
            return -1

        for d in range(4):
            next_rx, next_ry, r_count = move(rx, ry, x[d], y[d])  # 기울여서 이동했을 때 [끝지점의 x 좌표, y 좌표, 이동한 칸수]
            next_bx, next_by, b_count = move(bx, by, x[d], y[d])

            if board[next_bx][next_by] == 'O':  # blue가 구멍에 빠졌다면 해당 기울임(움직임) 무시
                continue
            if board[next_rx][next_ry] == 'O':
                return tilt_count

            # red와 blue가 같을 경우 이동 칸수가 많은 것(더 멀리서 온 것)을 한 칸 뒤로 빼줌
            if next_rx == next_bx and next_ry == next_by:
                if r_count > b_count:
                    next_rx -= x[d]
                    next_ry -= y[d]
                else:
                    next_bx -= x[d]
                    next_by -= y[d]

            # 각 기울임에 따라 도착하는 지점만을 visit 체크한다
            # 단 둘 중에 하나라도 방문하지 않은 지점이라면 가능한 기울임이라는 뜻이다
            if not visited[next_rx][next_ry][next_bx][next_by]:
                visited[next_rx][next_ry][next_bx][next_by] = 1
                queue.append([next_rx, next_ry, next_bx, next_by, tilt_count+1])


if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    board, red_first, blue_first = [], [], []
    visited = [[[[0 for _ in range(m)] for _ in range(n)] for _ in range(m)] for _ in range(n)]
    for i in range(n):
        tmp = sys.stdin.readline().rstrip()
        if 'R' in tmp:
            red_first = [i, tmp.index('R')]
        if 'B' in tmp:
            blue_first = [i, tmp.index('B')]
        board.append(tmp)

    print(bfs())

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

안전 영역이 나누어진 영역의 최댓값이라니 이런 무능한 재난청이 다 있나 싶었지만 어쨌든 문제를 풀었다.

문제를 풀 때 주의하거나 유의하면 좋을 점들은 다음과 같다.

1. 강수량 범위를 정해서 시작할 것

2. 전체 지역을 처음부터 검사하고 visited 배열을 만들어서 방문 체크를 하되 강수량 별로 초기화 할 것

3. dfs를 시작하는 지점도 visited 체크하는 것을 잊지 말 것

4. 각각의 안전한 지역 수를 셀 필요는 없음

import sys


# 비의 양(rain)에 따라 안전지대 수를 계산
def dfs(rain, row, col, check):
    stack = [[row, col]]

    while stack:
        r, c = stack.pop()
        for nR, nC in [[r+1, c], [r-1, c], [r, c+1], [r, c-1]]:
            if 0 <= nR < n and 0 <= nC < n:
                if not check[nR][nC]:
                    if board[nR][nC] > rain:
                        stack.append([nR, nC])
                check[nR][nC] = 1


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    board = []
    maxRain = 0  # max height
    # 최대 높이를 구하고 그것을 강수량 범위로 정한다
    for _ in range(n):
        tmp = list(map(int, sys.stdin.readline().split()))
        maxRain = max(maxRain, max(tmp))
        board.append(tmp)

    maxSafe = 0
    for rain in range(maxRain):
        safeZone = 0
        visited = [[0 for _ in range(n)] for _ in range(n)]  # 강수량 별로 초기화
        for i in range(n):
            for j in range(n):
                if not visited[i][j] and board[i][j] > rain:  # 침수 아닌 지역부터 시작
                    visited[i][j] = 1  # dfs를 시작하는 지점도 방문 체크를 잊지 말 것
                    dfs(rain, i, j, visited)
                    safeZone += 1
        maxSafe = max(maxSafe, safeZone)

    print(maxSafe)