2차원 맵에서 영역 구하기 (col-DFS)
2차원 맵에서 영역 구하기 (col-DFS) — #2차원배열 #2차원범위구분 #코딩테스트 #개발자의도구들 사용된 언어: 코틀린, 혹은 파이썬 순서: 로직, ...
#LeetCode#Naver Blog
#2차원배열 #2차원범위구분 #코딩테스트 #개발자의도구들
- 사용된 언어: 코틀린, 혹은 파이썬
- 순서: 로직, 코드 구현, 코드 분석
아이디어
프로그래머스 \[PCCP 기출문제\] 2번 / 석유 시추
https://school.programmers.co.kr/learn/courses/30/lessons/250136
💡 두 가지 방법
1. 다 아는 상태에서 탐색
-- 모두 탐색 후 영역을 나눠둔다.
-- 영역이 나눠질 때 좌표쌍을 저장해둠
-- col 좌표별로 전체 석유를 계산하면된다.
2. 매번 탐색하기
-- col별로 탐색을 시작
-- 1을 만나면 DFS 시전
-- 0을 만나면 무시하고 내려간다.
-- 반복해서 최종 결과값 계산
음.. 2번으로 하는게 나은거 같다.
1번으로 하기에는 메모리 사용량이 너무 많기도 하고, 복잡도가 너무 증가한다. 2번의 경우는 반복해서 DFS를 탐색해야하므로 비효율적일 수 잇지만, 빠르고 단순하게 구현이 가능해진다.
2번 로직 정리
💡 DFS로 빠르게 탐색
석유 카운트 - max로 계속 갱신
1. col별로 탐색을 시작한다.
-- for i in range(col)
2. 0을 만나면 내려간다
-- row++
3. 1을 만나면 DFS 시작
-- visited
-- stack
⚠️ DFS의 0과 시추시의 0을 구분할 것
1차 시도
def solution(land):
move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
answer = -1
totalCol = len(land[0])
totalRow = len(land)
# crt = col
for i in range(totalCol):
# start
now_x, now_y = 0, i
visited = [[0 for y in range(totalCol)] for x in range(totalRow)]
col_max = 0
while now_x < totalRow:
# chekc one or zero
if visited[now_x][now_y] == 1:
now_x += 1
continue
visited[now_x][now_y] = 1
if land[now_x][now_y] == 0:
now_x += 1
continue
# dfs start when one
position = [(now_x, now_y)]
while position:
cx, cy = position.pop()
col_max += 1
for i in range(4):
nx, ny = cx + move[i][0], cy + move[i][1]
if nx < 0 or ny < 0 or nx >= totalRow or ny >= totalCol:
continue
if visited[nx][ny] == 1 or land[nx][ny] == 0:
continue
position.append((nx, ny))
visited[nx][ny] = 1
now_x += 1
answer = max(answer, col_max)
return answer
- 1차 시도 결과로 정확성에서는 모두 만점이었으나, 효율성에서는 모두 틀렸다.
- 이번 문제에서 처음으로 효율성 테스트를 한다는 것을 알게되었다.
효율적이지 못하다는 것은 알고 잇었는데... 어디서 효율성에 문제가 크게 생기는 걸까?
✏️ 시간 복잡도 분석
1. n = 500, m = 500
최대 250,000번의 탐색이 매 col마다 이뤄진다.
500 * 250,000 = 최대 125,000,000의 탐색
1억번의 탐색 -> 탐색이 너무 많다.
효율성을 높이는 방법을 찾자.
탐색 횟수가 너무 많다.... 탐색횟수를 줄여가는 방법으로 고안해보자.
💡 new Idea
1. 가장 첫 위치 (0, 0)에서 탐색을 시작하여 모든 석유 위치를 indexing한다.
2. list, set등을 이용하여 석유 영역을 분리해 둔다.
-- 총 석유의 수는 len으로 구하면 된다.
3. col i에 대한 전체 석유 수를 구하려면 아래 절차를 따른다.
-- a. 모든 list를 탐색하여 col i에 해당하는 좌표가 있는지 확인한다.
-- b. 있다면, 해당 list의 len을 구한다.
-- c. 모든 col i에 대해 반복한다.
2차시도
def solution(land):
move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
answer = -1
totalCol = len(land[0])
totalRow = len(land)
oil_positions = [] # [[(x, y), (x, y) ...]]
visited = [[0 for y in range(totalCol)] for x in range(totalRow)]
for i in range(totalRow):
for j in range(totalCol):
if visited[i][j] == 1:
continue
if land[i][j] == 1:
visited[i][j] = 1
oils = [(i, j)]
stack = [(i, j)]
while stack:
x, y = stack.pop()
for s in range(4):
nx, ny = x + move[s][0], y + move[s][1]
if nx < 0 or ny < 0 or nx >= totalRow or ny >= totalCol:
continue
if land[nx][ny] == 0 or visited[nx][ny] == 1:
continue
stack.append((nx , ny))
oils.append((nx, ny))
visited[nx][ny] = 1
oil_positions.append(oils)
print(oil_positions)
for i in range(totalCol): # 상수 x
col_max = 0
for position in oil_positions: # n
is_find = False
for ps in position:
if i == ps[1]:
is_find = True
break
if is_find:
col_max += len(position)
answer = max(answer, col_max)
return answer
- 전략을 수정했으나 효율성에서 실패했다.
- 코드를 짜고 보닌깐 효율적인 것 같은 코드 역시도 반복문이 너무 많다는 것을 깨달았다.
✒️ 시간 복잡도
- n,m = 500
1. 처음 update 하는 for문 -> 500 * 500 = 250,000
2. dfs -> 1번에 포함됨
3. col을 체크하는 곳 -> i는 최대 500번, positions의 길이는 최대 500
이역시 500 * 500 = 250,000으로 분석된다.
❌ 그럼 총 500,000번의 연산이 기대되는 것으로 보이는데.. 화실히 연산 횟수가 줄어들었다.
👉 영역이 모두 1인 경우를 생각하자 -> [[x, y], [x1,y1], [x2,y2]...] 이게 250,000개 존재함
totalCol이 500이므로 결국에는 1번 경우와 똑같이 500 * 250,000번의 탐색이 이루어진다...!
last dance
🕺💃
거의 다왔다. 하지만 열체크하는 전략이 아쉬웠다. 마지막 전략은 Gpt-o3-mini의 도움을 받아서 찾아낸 전략이다.
🔑 마지막 for문을 수정하는 것이 핵심 목표
✅ oil_positions만 순회한다.
✅ col_oil = [0] * totalCol로 선언
✅ oil_positions를 참고하여 col_oil을 갱신한다.
def solution(land):
move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
totalCol = len(land[0])
totalRow = len(land)
oil_positions = [] # [[(x, y), (x, y) ...]]
visited = [[0 for y in range(totalCol)] for x in range(totalRow)]
for i in range(totalRow):
for j in range(totalCol):
if visited[i][j] == 1:
continue
if land[i][j] == 1:
visited[i][j] = 1
oils = [(i, j)]
stack = [(i, j)]
while stack:
x, y = stack.pop()
for s in range(4):
nx, ny = x + move[s][0], y + move[s][1]
if nx < 0 or ny < 0 or nx >= totalRow or ny >= totalCol:
continue
if land[nx][ny] == 0 or visited[nx][ny] == 1:
continue
stack.append((nx , ny))
oils.append((nx, ny))
visited[nx][ny] = 1
oil_positions.append(oils)
col_oil = [0] * totalCol
for position in oil_positions: # n
visited = [0] * totalCol
for ps in position:
col = ps[1]
if visited[col] == 1:
continue
col_oil[col] += len(position)
visited[col] = 1
return max(col_oil)
정답이다!
마지막에 다 구해놓고 시간 복잡도를 충분히 고려하지 못한게 좀 아쉽지만, 그래도 스스로 거의 다 풀어서 만좁한다!