classSolution:defproductExceptSelf(self, nums: List[int]) -> List[int]:
ans = 1
cnt_zero = 0for i inrange (0,len(nums)):
if nums[i] == 0:
cnt_zero += 1else:
ans *= nums[i]
answer = []
if cnt_zero == 0:
for i inrange (0,len(nums)):
t = ans // nums[i]
answer.append(t)
elif cnt_zero == 1:
for i inrange (0,len(nums)):
if nums[i] == 0:
answer.append(ans)
else:
answer.append(0)
else:
for i inrange (0,len(nums)):
answer.append(0)
return answer
from collections import deque
defsolution(prices):
answer = []
prices = deque(prices)
while prices:
x = prices.popleft()
count = 0for i in prices:
if x > i:
count += 1break
count += 1
answer.append(count)
return answer
from collections import deque
N,K = map(int,input().split())
num = [0for _ inrange (0,100001)]
deq = deque()
deq.appendleft(N)
while deq:
X = deq.popleft()
if X == K:
print(num[K])
else:
for a in (X-1,X+1,2*X):
if0 <= a <= 100000and num[a] == 0:
num[a] = num[X] + 1
deq.append(a)
import sys
N,M = map(int, input().split())
num = {}
name = {}
for i inrange(1,N+1):
pokemon = input()
num[i] = pokemon
name[pokemon] = i
for _ inrange (0,M):
x = input()
if x.isdigit():
print(num[int(x)])
else:
print(name[x])
import copy
from collections import deque
deforangesRotting(m,n,grid):
checked = [[Falsefor _ inrange (0,n)] for _ inrange (0,m)]
deq = deque()
a = []
fresh = 0for i inrange (0,m):
for j inrange (0,n):
if grid[i][j] == 0:
fresh += 1if grid[i][j] == 1:
a.append([i,j])
deq.append(a)
dx = [0,0,1,-1]
dy = [1,-1,0,0]
day = 0#이미 다 상해있는 경우if fresh == 0:
return day
#그렇지 않은 경우while deq:
k = fresh
x = deq.popleft()
rotten_orange = []
for i inrange (0,len(x)):
for j inrange (0,4):
a = x[i][0] + dx[j]
b = x[i][1] + dy[j]
if0 <= a < m and0 <= b < n and grid[a][b] == 0 :
grid[a][b] = 1
fresh -= 1
rotten_orange.append([a,b])
if k == 0:
breakif k == fresh:
return -1else:
day += 1
deq.appendleft(rotten_orange)
return day
M,N = map(int,input().split())
A = []
for i inrange (0,N):
a = list(map(int,input().split()))
A.append(a)
print(orangesRotting(N,M,A))
import sys
input = sys.stdin.readline
N = int(input())
cut_paper = []
n = N
while n > 0:
A,B = [[0for _ inrange (0,n)] for _ inrange (0,n)], [[1for _ inrange (0,n)] for _ inrange (0,n)]
n = n//2
a = []
a.append(A)
a.append(B)
cut_paper.append(a)
paper = []
for i inrange (0,N):
a = list(map(int,input().split()))
paper.append(a)
cutted = [[Falsefor _ inrange (0,N)] for _ inrange (0,N)]
M = len(cut_paper)
cnt_blue = 0
cnt_white = 0for i inrange (0,M): #큰 사각형부터 크기를 쪼개보기for x inrange (0,N,len(cut_paper[i][0])):
for y inrange (0,N,len(cut_paper[i][0])):#사각형의 꼭짓점 정하기 (x,y로 셋팅)
jud1 = True
jud2 = Truefor j inrange (0,len(cut_paper[i][0])):
for k inrange (0,len(cut_paper[i][0])):
if cut_paper[i][0][j][k] == paper[x+j][y+k] and cutted[x+j][y+k] == False: #흰색인지 확인continueelse:
jud1 = Falsebreakfor j inrange (0,len(cut_paper[i][0])):
for k inrange (0,len(cut_paper[i][0])):
if cut_paper[i][1][j][k] == paper[x+j][y+k] and cutted[x+j][y+k] == False: #파란색인지 확인continueelse:
jud2 = Falsebreakif jud1 == True:
for j inrange (0,len(cut_paper[i][0])):
for k inrange (0,len(cut_paper[i][0])):
cutted[x+j][y+k] = True#흰색인지 확인
cnt_white += 1if jud2 == True:
for j inrange (0,len(cut_paper[i][0])):
for k inrange (0,len(cut_paper[i][0])):
cutted[x+j][y+k] = True#파란색인지 확인
cnt_blue += 1print(cnt_white)
print(cnt_blue)
import sys
import math
input = sys.stdin.readline
N = int(input())
M = int(input())
A = [[math.inf for _ inrange (0,N)] for _ inrange (0,N)]
for i inrange (0,M):
a,b,c = map(int,input().split())
if A[a-1][b-1] == math.inf:
A[a-1][b-1] = c
else:
A[a-1][b-1] = min(c,A[a-1][b-1])
for k inrange (0,N):
for i inrange (0,N):
for j inrange (0,N):
if i == j:
A[i][j] = 0else:
A[i][j] = min(A[i][j], A[i][k] + A[k][j])
for i inrange (0,N):
for j inrange (0,N):
if A[i][j] == math.inf:
A[i][j] = 0for i inrange (0,len(A)):
print(" ".join(str(s) for s in A[i]))
defsolution(elements):
ans = []
for i inrange (0,len(elements)):
ans.append(elements[i])
for i inrange (0,len(elements)):
ans.append(elements[i])
summary = []
for i inrange (0,len(elements)): #길이를 indicatefor j inrange (1,len(elements)+1): #시작index 저장
a = sum(ans[i:i+j])
summary.append(a)
summary = list(set(summary))
answer = len(summary)
return answer
classSolution:import math
defthreeSumClosest(self, nums: List[int], target: int) -> int:
N = len(nums)
nums.sort()
max_diff = 20001
ans = 0for i inrange (0,N):
start = i + 1
end = N - 1while start < end:
summary = nums[i] + nums[start] + nums[end]
c = int(math.fabs(summary - target))
if summary == target:
return target
else:
if c < max_diff:
max_diff = c
ans = summary
if summary < target:
start += 1else:
end -= 1return ans
5. Reduction Operations to Make the Array elements equal
defsolution(n, left, right):
answer = []
cnt = -1
a,b = left // n, left % n
c,d = right// n , right % n
cnt = -1 + a * n
for i inrange (a,c+1):
for j inrange (0,n):
cnt += 1if left <= cnt <= right:
answer.append(max(j+1,i+1))
if cnt == right:
breakreturn answer
classSolution:import heapq
deffindKthLargest(self, nums: List[int], k: int) -> int:
heap = []
for i inrange (0,len(nums)):
heapq.heappush(heap,-nums[i])
for i inrange (0,k-1):
heapq.heappop(heap)
a = -heapq.heappop(heap)
return a
classSolution:import heapq
defkthSmallest(self, matrix: List[List[int]], k: int) -> int:
heap = []
for i inrange (0,len(matrix)):
for j inrange (0,len(matrix[0])):
heapq.heappush(heap,matrix[i][j])
for i inrange (0,k-1):
heapq.heappop(heap)
a = heapq.heappop(heap)
return a
import sys
input = sys.stdin.readline
S = input().rstrip()
M = input().rstrip()
n = len(S)
m = len(M)
com = []
for i inrange (0,m):
com.append(M[i])
result = []
if n >= m:
for s in S:
result.append(s)
if result[-m:] == com:
for i inrange (0,m):
result.pop(-1)
u = "".join(t for t in result)
else:
for s in S:
result.append(s)
u = "".join(t for t in result)
if u == "":
print("FRULA")
else:
print(u)
from collections import deque
M,N,K = map(int,input().split())
A = [[0for _ inrange (0,N)] for _ inrange (0,M)]
visited = [[Falsefor _ inrange (0,N)] for _ inrange (0,M)]
for i inrange (0,K): #벽(색칠된 부분) 체크하기
a = list(map(int,input().split()))
for j inrange (a[1],a[3]):
for k inrange (a[0],a[2]):
A[j][k] = 1
dx = [0,0,1,-1]
dy = [1,-1,0,0]
ans = []
for i inrange (0,M):
for j inrange (0,N):
if A[i][j] == 0and visited[i][j] == False:
cnt = 1
deq = deque()
deq.appendleft((i,j))
while deq:
x,y = deq.popleft()
visited[x][y] = Truefor k inrange (0,4):
a = x + dx[k]
b = y + dy[k]
if0 <= a < M and0 <= b < N:
if A[a][b] == 1:
continueif visited[a][b] == Falseand A[a][b] == 0:
deq.appendleft((a,b))
visited[a][b] = True
cnt += 1
ans.append(cnt)
ans.sort()
print(len(ans))
print(" ".join(str(s) for s in ans))
어떤 점의 좌표가 주어져있을 때, 그 점의 상하좌우를 전부 훑어보면서 방문한 곳인지 방문하지 않은 곳인지 체크하면서
deque에 추가해주면 됩니다. 방법은 dfs던 bfs던 상관 없을 것 같습니다.
처음으로 방문한 곳은 방문처리를 해서 이후에 올 수 없도록 하는 조치가 필요하겠습니다.
몇개가 붙어있는지 세면 되기 때문에, cnt를 통해 인접한 영역의 갯수를 구하면서 리스트 ans에 추가하면 되겠습니다.
ans를 오름차순으로 정렬해준 뒤, 출력해주면 되겠습니다.
2. 프로그래머스 - 미로 탐색
from collections import deque
defsolution(maps):
answer = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
deq = deque()
deq.append((0, 0))
n = len(maps) #세로 길이 first component
m = len(maps[0]) #가로 길이 second component
check = [[Falsefor _ inrange (0,m)] for _ inrange (0,n)]
while deq:
x,y = deq.popleft()
check[x][y] = Truefor i inrange(0,4):
a = x + dx[i]
b = y + dy[i]
if0 <= a < n and0 <= b < m:
if maps[a][b] == 0:
continueelse:
if check[a][b] == False:
maps[a][b] += maps[x][y]
check[a][b] = True
deq.append((a,b))
else:
maps[a][b] = min(maps[a][b], maps[x][y] + 1)
else:
continueif maps[-1][-1] == 1:
return -1else:
return maps[-1][-1]
N,M = map(int,input().split())
A = []
for i inrange (0,N):
a = input()
b = []
for j inrange (0,len(a)):
b.append(int(a[j]))
A.append(b)
print(solution(A))
동일하게 상하좌우로 막히지 않은 곳을 찾아가면서 도착점까지 가면 되겠습니다.
주의해야할 점은, 이미 방문한 포인트에 있어서는 어떻게 해야하는가? 가 되겠습니다.
그때는 기존값과 새롭게 취한 루트에 대해서의 값을 비교해주면 되겠습니다.
그리고 deque가 비워졌음에도 불구하고 도달하지 못한 경우에는 출구에 도달하지 못했다는 뜻이 되겠습니다.
3. 프로그래머스 - 무인도 여행
from collections import deque
defsolution(maps):
answer = []
N = len(maps)
A = [[0for _ inrange (0,len(maps[0]))] for _ inrange (0,N)]
for i inrange (0,N):
for j inrange (0,len(maps[0])):
if maps[i][j] == "X":
A[i][j] = "X"else:
A[i][j] = int(maps[i][j])
M = len(maps[0])
visited = [[Falsefor _ inrange (0,M)] for _ inrange (0,N)]
#first ex: n = 4, m = 5
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for i inrange (0,N):
for j inrange (0,M):
if A[i][j] == "X"or visited[i][j] == True:
continueelse:
cnt = A[i][j]
deq = deque()
deq.appendleft((i,j))
while deq:
x,y = deq.popleft()
visited[x][y] = Truefor k inrange (0,4):
a = x + dx[k]
b = y + dy[k]
if0 <= a < N and0 <= b < M:
if visited[a][b] == Falseand A[a][b] != "X":
deq.appendleft((a,b))
visited[a][b] = True
cnt += A[a][b]
answer.append(cnt)
answer.sort()
if answer == []:
return [-1]
else:
return answer
1번과 동일한 유형입니다.
단순히 이 경우에는 각 좌표 i,j에 방문할때마다 cnt에 A_ij에 해당하는 값을 더해주면 됩니다.
이후, cnt 값을 리스트에 추가하면서 오름차순으로 정렬하면 정답이 나옵니다.
4. 프로그래머스 - 네트워크
from collections import deque
defsolution(n, computers):
answer = 0
connection = []
for i inrange (0,n):
a = []
deq = deque()
deq.append((i,i))
checked = [[Falsefor _ inrange (0,n)] for _ inrange (0,n)]
checked[i][i] = True
a.append(i)
while deq:
x,y = deq.popleft()
a.append(y)
for z inrange (0,n) :
if computers[y][z] == 1and checked[y][z] == False:
deq.append((y,z))
checked[y][z] = True
a.append(z)
else:
continue
a = list(set(a))
connection.append(a)
ans = []
for i inrange (0,len(connection)):
if connection[i] in ans:
continueelse:
ans.append(connection[i])
answer = len(ans)
return answer
이 경우에는 Directed graph가 아닌 Undirected Graph입니다.
예를 들어, i와 j가 연결되어있다 한다면 행렬을 만들 때 A_ij = A_ji = 1로서 설정하는 방식으로 행렬 A를 구성해줍니다.
이런 행렬 A를 Adjacency Matrix 인접행렬 이라고 부릅니다.
결국 각 노드에 방문했을 때 이어져있는 모든 노드를 찾아보는 방식이 되겠습니다.
그렇게 노드의 끝이 어디인지 찾아가는 방식이 되겠네요.
(이 과정에서 연산이 조금 많아질 수 있는데, 이런 경우에는 처음에 A를 받아올 때,
A = [[] for _ in range 0,N] 이렇게 빈 매트릭스를 만들어준 뒤에, A[i]에 대해서만 사이클을 돌려주면 될 것 같습니다.)
5. 백준 - 케빈 베이컨의 6단계 법칙
import sys
import math
input = sys.stdin.readline
N,M = map(int,input().split())
A = [[math.inf for _ inrange (0,N)] for _ inrange (0,N)]
for i inrange (0,M):
a,b = map(int,input().split())
A[a-1][b-1],A[b-1][a-1] = 1,1for k inrange (0,N):
for i inrange (0,N):
for j inrange (0,N):
A[i][j] = min(A[i][j], A[i][k] + A[k][j])
answer = []
for i inrange (0,N):
a = sum(A[i]) - A[i][i]
answer.append(a)
min_val = min(answer)
for i inrange (0,N):
if answer[i] == min_val:
print(i+1)
break
위에서 언급한 Adjacency Matrix의 예 입니다.
친구라는 것이 단방향이 아니라 양방향으로 알고 있는 것을 전제로 하고 있기 때문에, 이렇게 생각해볼 수 있겠습니다.
한편, 행렬 2개를 곱해주면서 그 값이 어떻게 되는지 체크하는 것이겠습니다.
아이디어로서는 i와 j가 알고있고, j가 k가 알고 있다고 하는 상황에서, i와 k의 관계가 어떨까요?
설명조금더작성
6. 백준 - 내리막 길 골드3
deff(x,y):if x == M-1and y == N-1:
return1if dp[x][y] != -1:
return dp[x][y]
route = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for i inrange (0,4):
a = x + dx[i]
b = y + dy[i]
if0 <= a < M and0 <= b < N and graph[x][y] > graph[a][b]:
route += f(a,b)
dp[x][y] = route
return route
M,N = map(int,input().split())
graph = []
dp = [[-1for _ inrange (0,N)] for _ inrange (0,M)]
for i inrange (0,M):
a = list(map(int,input().split()))
graph.append(a)
print(f(0,0))
7. Leet code - Rotting Oranges medium
classSolution:import copy
from collections import deque
deforangesRotting(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
checked = [[Falsefor _ inrange (0,n)] for _ inrange (0,m)]
deq = deque()
a = []
fresh = 0for i inrange (0,m):
for j inrange (0,n):
if grid[i][j] == 1:
fresh += 1if grid[i][j] == 2:
a.append([i,j])
deq.append(a)
dx = [0,0,1,-1]
dy = [1,-1,0,0]
day = 0#이미 다 상해있는 경우if fresh == 0:
return day
#그렇지 않은 경우while deq:
k = fresh
x = deq.popleft()
rotten_orange = []
for i inrange (0,len(x)):
for j inrange (0,4):
a = x[i][0] + dx[j]
b = x[i][1] + dy[j]
if0 <= a < m and0 <= b < n and grid[a][b] == 1 :
grid[a][b] = 2
fresh -= 1
rotten_orange.append([a,b])
if k == 0:
breakif k == fresh:
return -1else:
day += 1
deq.appendleft(rotten_orange)
return day
상한 오렌지는 상하좌우에 있는 오렌지를 전부 상하게 한다는 점에 착목하면 좋을 것 같습니다.
8. 프로그래머스 - 게임 맵 최단거리
from collections import deque
defsolution(maps):
answer = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
deq = deque()
deq.append((0, 0))
n = len(maps) #세로 길이 first component
m = len(maps[0]) #가로 길이 second component
check = [[Falsefor _ inrange (0,m)] for _ inrange (0,n)]
while deq:
x,y = deq.popleft()
check[x][y] = Truefor i inrange(0,4):
a = x + dx[i]
b = y + dy[i]
if0 <= a < n and0 <= b < m:
if maps[a][b] == 0:
continueelse:
if check[a][b] == False:
maps[a][b] += maps[x][y]
check[a][b] = True
deq.append((a,b))
else:
maps[a][b] = min(maps[a][b], maps[x][y] + 1)
else:
continueif maps[-1][-1] == 1:
return -1else:
return maps[-1][-1]
9. Leet code - Course Schedule medium
classSolution:fromcollections import dequedefcanFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:v = numCoursese = len(prerequisites)graph = [[] for _ in range (0,v)]indegree = [0 for _ in range (0,v)]foredge in prerequisites:a,b = edge[0],edge[1]graph[a].append(b)indegree[b]+= 1deq = deque()fori in range (0,v):ifindegree[i] == 0:deq.appendleft(i)result = []print(deq)iflen(deq) == 0:returnFalseA = []whiledeq:now = deq.popleft()result.append(now)fori in graph[now]:indegree[i]-= 1ifindegree[i] == 0:deq.appendleft(i)iflen(result) != v:returnFalsereturnTrue
위상정렬 Topologicalsort에 대한 개념을 알 수 있었습니다.
일반적인 DFS, BFS와 비슷한 느낌이지만 directed graph를 설정한 후, Route의 끝까지 뚫는 역할을 합니다.
10. 백준 - 전쟁전투 실버1
from collections import deque
N,M = map(int,input().split())
check= [[Falsefor _ inrange (0,N)] for _ inrange (0,M)]
war = []
for i inrange (0,M):
a = input()
war_list = []
for j inrange (0,len(a)):
war_list.append(a[j])
war.append(war_list)
power1 =0
power2 =0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for i inrange (0,M):
for j inrange (0,N):
if war[i][j] == "W" andcheck[i][j] ==False:
check[i][j] =True
deq = deque()
deq.append((i,j))
cnt =0
while deq:
x,y = deq.popleft()
cnt +=1for k inrange (0,4):
a = x + dx[k]
b = y + dy[k]
if 0<= a < M and0<= b < N andcheck[a][b] ==Falseand war[a][b] == "W":
deq.append((a,b))
check[a][b] =True
power1 += cnt **2
if war[i][j] == "B" andcheck[i][j] ==False:
check[i][j] =True
deq = deque()
deq.append((i,j))
cnt =0
while deq:
x,y = deq.popleft()
cnt +=1for k inrange (0,4):
a = x + dx[k]
b = y + dy[k]
if 0<= a < M and0<= b < N andcheck[a][b] ==Falseand war[a][b] == "B":
deq.append((a,b))
check[a][b] =True
power2 += cnt **2
print(power1,power2)
11. 백준 - 숨바꼭질 2 골드5
from collections import deque
N,K = map(int,input().split())
if N >= K:
print(N-K)
print(1)
else:
cnt = 0
num = [0for _ inrange (0,100001)]
deq = deque()
deq.appendleft([N])
while deq:
X = deq.popleft() #리스트로 받아옴
B = []
for i inrange (0,len(X)):
for y in (X[i] - 1, X[i] + 1, 2 * X[i]):
if y > 100000or y < 0:
passelse:
if num[y] == 0or num[y] == num[X[i]] + 1:
B.append(y)
if y == K:
cnt += 1
num[y] = num[X[i]] + 1else:
if y == K:
cnt += 1
deq.appendleft(B)
if cnt != 0:
breakelse:
continueprint(num[K])
print(cnt)
12. 프로그래머스 - 타겟 넘버
from collections import deque
defsolution(numbers, target):
answer = 0
deq = deque()
deq.append([numbers[0],-numbers[0]])
cnt = 1while cnt < len(numbers):
A = deq.popleft()
B = []
for i inrange (0,len(A)):
B.append(A[i]-numbers[cnt])
B.append(A[i]+numbers[cnt])
deq.append(B)
cnt += 1for i inrange (0,len(deq[0])):
if deq[0][i] == target:
answer += 1return answer
#풀이 1 (Yellow 활용)
import math
def solution1(brown, yellow):
a = brown + yellow #전체 타일 갯수 afor i in range (1,int(math.sqrt(a))+1): #a = i * (a//i) = i * b (i <= b)if a % i == 0:
b = a // i
if (i - 2) * (b - 2) == yellow: #yellow = (i-2) * (b-2)
answer = [b,i]
return answer
#풀이 2 (전체 활용)
def solution2(brown,yellow):
for i in range (1,int(math.sqrt(yellow))+1): #yellow = i * (yellow//i) = i * b (i <= b)if yellow % i == 0:
b = yellow // i
if (i + 2) * (b + 2) == brown + yellow: #brown + yellow = (i+2) * (b+2)
answer = [b+2,i+2]
return answer
brown,yellow = map(int,input().split())
print(solution1(brown,yellow))
print(solution2(brown,yellow))
첫 번째는, Yellow 타일과 Brown 타일의 개수를 합친다면 전체 타일 개수가 나온다는 점을 활용하는 풀이
주목할 점은 Yellow 타일의 개수 = 타일의가로길이−2 * 타일의세로길이−2라는 점입니다.
그래서, 전체 타일 갯수 a = i * a//i가로x세로로 나눈 뒤,
yellow = i−2 * a//i−2가 되는지 확인하는 방법입니다.
두 번째는, 첫 번째의 반대 순서로 생각해내가는 방법입니다.
브루트포스 방법으로 한다면, 아마 다음과 같이 되지 않을까 싶습니다.
이후, 따로 준비한 문제 두 개는 백준 1051번 숫자 정사각형 실버3, 백준 2468 안전 영역 실버1이다.
숫자 정사각형은 정직하게 풀면 쉽게 풀리고, 안전 영역은 DFS, BFS와 연관 지을 수 있기 때문에 추가적으로 학습했다.
2. 숫자 정사각형
#BOJ 1051 숫자정사각형 실버3
N,M = map(int,input().split())
A = []
for i in range (0,N):
a = list(str(input()))
A.append(a)
ans = []
for i in range (1,N+1):
for x in range (0,N-i+1):
for y in range (0,M-i+1):
B = list(set([A[x][y],A[x][y+i-1],A[x+i-1][y],A[x+i-1][y+i-1]]))
if len(B) == 1:
ans.append(i*i)
else:
continueprint(max(ans))
아이디어는 n * n 정사각형을 생각 한 뒤, 각 정사각형의 꼭짓점이 시작점A[i][j]을포함하여 A[i][j+n-1],A[i+n-1][j] , A[i+n-1][j+n-1] 으로 나타내어진다는 것에 주목하면 좋다.
만약, 위 네점에 해당하는 값이 전부 같다면, set 함수를 사용하여 중복되는 값들을 전부 삭제할 수 있기 때문에 set−의 길이는 1이 되겠다.
하지만 한 점이라도 해당하는 값이 다르다면, set에 의해 만들어지는 튜플의 길이가 2 이상이 되기 때문에 간단하게 판단할 수 있다.
이후, 만약 set에 의해 생성되는 튜플의 길이가 1이라면 정사각형의 넓이는 n * n 으로 주어지므로 이를 ans에 추가.
혹은max함수를사용하는것도좋아보인다.
그 뒤 ans의 최댓값을 반환하면 끝.
3. 안전 지대
from collections import deque
N = int(input())
A = []
max_height = 0
for i in range (0,N):
a = list(map(int,input().split()))
max_height = max(max(a),max_height)
A.append(a)
def move(x,y,h):
dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
z = []
for i in range (0,4):
a = x + dxdy[i][0]
b = y + dxdy[i][1]
if 0 <= a < N and 0 <= b < N and A[a][b] > h:
z.append([a,b])
return z
ans = []
for height in range (0,max_height):
cnt = 0
visited = [[False for _ in range (0,N)] for _ in range (0,N)]
for i in range (0,N):
for j in range (0,N):
if A[i][j] > height and visited[i][j] == False:
visited[i][j] = True
a = deque([])
a.appendleft([i,j])
while a:
c = a.popleft()
visited[c[0]][c[1]] = True
b = move(c[0],c[1],height)
for area in b:
if visited[area[0]][area[1]] == False:
visited[area[0]][area[1]] = True
a.appendleft([area[0],area[1]])
cnt += 1
ans.append(cnt)
print(max(ans))
아이디어는 다음과 같다.
1. 최고 높이 max_height 구하기 for문을통해0maxheight까지전부체크하기위함
2. DFS, BFS를 통하여 연결 요소의 갯수를 구하기
이과정에서높이가1에서구한변수보다높은지판정이필요함
3. 연결요소의 갯수를 저장하는 리스트를 만든 뒤, 그 뒤 최댓값 반환
느낀 점
브루트포스 알고리즘에서 백트래킹 끝까지탐색을완료하면뒤로돌아가는에 관련된 문제가 많았다는 것을 알 수 있었다.
또한 DFS,BFS와 연계되어있는 문제가 많아 보이므로 그 부분에 대해 추가 공부를 하는 것도 좋아 보인다.
