[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파
START :
[3코1파] 2023.01.04~ (304일차)
[4코1파] 2023.01.13~ (296일차)
[4코3파] 2023.10.01 ~ (34일차)
Today :
2023.11.03 [304일차]
Leetcode Graph
[1] 200. Number of Islands
문제 설명
2차원 그리드(매트릭스)가 주어지고, 이 그리드에서 섬(1로 표시된 영역)의 수를 계산하는 문제이다.
'1'은 물 위에 존재하는 섬을 나타내고, '0'은 물이다. 섬은 수평 또는 수직으로 인접한 '1'로 이루어진 영역인데, 섬들 간의 대각선으로 인접한 경우에는 하나의 섬으로 간주한다.
문제 풀이 방법
그래프 탐색 문제로, 대표적으로 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS) 알고리즘을 사용하여 해결할 수 있다. 여기서는 dfs로 해결했다.
dfs 를 나가는 조건은 들렀던 좌표, 그리드 범위를 넘어가는 좌표, 물인 좌표이고 해당 좌표에서 동서남북으로 dfs로 움직이면서 섬의 개수를 더하고 그리드를 다 돈 후의 섬의 개수를 반환한다.
내 코드
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
visited = set()
ans = 0
def dfs(r,c):
if r<0 or c<0 or r==ROWS or c==COLS or (r,c) in visited or grid[r][c]=='0':
return
visited.add((r,c))
dfs(r-1,c)
dfs(r+1,c)
dfs(r,c-1)
dfs(r,c+1)
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == '1' and (r,c) not in visited:
ans +=1
dfs(r,c)
return ans
[2] 133. Clone Graph
문제 설명
문제 풀이 방법
내 코드
[3] 695. Max Area of Island
https://leetcode.com/problems/max-area-of-island/description/
문제 설명
0과 1로 이루어진 2D 그리드에서 섬(1로 표시된 영역)의 최대 면적을 반환한다.
문제 풀이 방법
주어진 2D 그리드를 순회하면서 1을 발견하면 해당 지점을 시작점으로 설정하여 DFS를 수행한다.
DFS는 현재 위치에서 출발하여 연결된 모든 1을 방문하며 그 개수를 세고, 이를 현재 섬의 면적으로 계산한다. DFS를 재귀로 탐색하여 연결된 모든 1을 방문하고, 이 과정에서 섬의 면적을 누적하면서 최대 면적을 업데이트 한다.
내 코드
시간복잡도와 공간복잡도는 그리드의 면적 O(M*N) 이다.
class Solution:
def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
visited = set()
maxArea = 0
def dfs(r,c):
if r<0 or c<0 or r==ROWS or c==COLS or grid[r][c]==0 or (r,c) in visited:
return 0
visited.add((r,c))
return dfs(r-1,c) + dfs(r+1,c) + dfs(r,c-1) + dfs(r,c+1) +1
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 1 and (r,c) not in visited:
maxArea = max(maxArea, dfs(r,c))
return maxArea
[4] 417. Pacific Atlantic Water Flow
문제 설명
주어진 2D 그리드에서 물이 대서양 또는 태평양으로 흐를 수 있는 모든 위치를 반환한다. 각 그리드에는 물의 높이의 양을 나타나 있는데 이웃 셀의 높이가 현재 셀의 높이보다 작거나 같으면 빗물이 바로 북쪽, 남쪽, 동쪽, 서쪽으로 이웃 셀로 흐를 수 있다. 물은 바다에 인접한 모든 세포에서 바다로 흐를 수 있다.
문제 풀이 방법
두 개의 2D 그리드로 하나는 대서양에서 시작하여 해당 지점에 물이 닿을 수 있는지에 대한 여부와 다른 하나는 태평양에서 시작하여 해당 지점에 물이 닿을 수 있는지 여부를 나타낸다.
대서양과 태평양에 닿을 수 있는 모든 위치를 찾기 위해 DFS 또는 BFS를 사용하는데, 대서양과 태평양의 시작 지점은 각각의 해안선에 위치한 지점이므로 대서양과 태평양에서 출발하여 그리드를 탐색하면서, 현재 위치에서 이웃한 위치로 물이 흐를 수 있는 경우에 대서양 또는 태평양에 닿을 수 있다고 표시한다.
최종적으로, 양쪽 해안에 도달할 수 있는 모든 지점을 식별하고 반환한다.
내 코드
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> list[list[int]]:
ROWS, COLS = len(heights), len(heights[0])
pac, atl = set(), set()
def dfs(r,c, visited, height):
if r<0 or c<0 or r==ROWS or c==COLS or heights[r][c] < height or (r,c)in visited:
return
visited.add((r,c))
dfs(r-1,c, visited, heights[r][c])
dfs(r+1,c, visited, heights[r][c])
dfs(r,c-1, visited, heights[r][c])
dfs(r,c+1, visited, heights[r][c])
for r in range(ROWS):
dfs(r, 0, pac, heights[r][0])
dfs(r,COLS-1, atl, heights[r][COLS-1])
for c in range(COLS):
dfs(0, c, pac, heights[0][c])
dfs(ROWS-1, c, atl, heights[ROWS-1][c])
ans = []
for r in range(ROWS):
for c in range(COLS):
if (r,c) in pac and (r,c) in atl:
ans.append((r,c))
return ans
[5] 130. Surrounded Regions
https://leetcode.com/problems/surrounded-regions/description/
문제 설명
주어진 2D 그리드에서 'X'로 둘러싸인 영역 'O'를 'X'로 변경한다.
상,하,좌,우 모두 'X'로 둘러싸인 영역만 변경해야하고, 아닌 'O'는 그대로 두어야 한다.
문제 풀이 방법
그리드를 순회하면서 그리드의 가장자리에 있는 'O'를 찾아야하는데, 이 'O'는 둘러싸인 영역이 아니므로, 바뀌면 안된다.
그래서 해당 'O'는 임시 문자 여기서는 'T'로 변경한다.
그리고 다시 그리드를 순회하면서 'O'를 'X'로 변경하고, 'T'로 바꾼 문자는 다시 'O'으로 되돌린다.
내 코드
class Solution:
def solve(self, board: list[list[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
ROWS, COLS = len(board), len(board[0])
def dfs(r,c):
if r<0 or c<0 or r==ROWS or c==COLS or board[r][c] !='O':
return
board[r][c] = 'T'
dfs(r-1,c)
dfs(r+1,c)
dfs(r,c-1)
dfs(r,c+1)
for r in range(ROWS):
for c in range(COLS):
if r in [0, ROWS-1] or c in [0,COLS-1] and board[r][c] == "O":
dfs(r,c)
for r in range(ROWS):
for c in range(COLS):
if board[r][c] == 'O':
board[r][c] = 'X'
for r in range(ROWS):
for c in range(COLS):
if board[r][c] == 'T':
board[r][c]= 'O'
[6] 994. Rotting Oranges
문제 설명
그리드에서 오렌지가 썩을 때까지 시간을 측정하는 문제이다.
비워져있는 셀은 0, 신선한 오렌지는 1, 썩은 오렌지는 2를 나타낸다.
썩은 오렌지는 상하좌우로 인접한 오렌지를 썩히는데 1 time이 걸린다.
그리드 내의 모든 오렌지를 썩히는 시간을 측정하고, 다 썩지 못하게 한다면 -1을 반환한다.
문제 풀이 방법
해당 문제는 썩은 오렌지가 2개 이상 있을 경우, 주변 오렌지를 썩게하는 프로세스가 동시에 일어날 수 있어 '동시성'을 고려해야 한다.
이때는 DFS(깊이 우선 탐색) 으로 해결하기 어려운데, DFS는 보통 한 노드를 방문하고 그 이웃 노드를 방문하는 순차적인 방식으로 동작하기 때문에 동시성을 고려하기 어렵다.
반면에 BFS(너비 우선 탐색)의 경우에는, 레벨 단위로 탐색하고, 각 레벨에서 모든 노드를 동시에 처리할 수 있기 때문에 '동시성'을 고려할 수 있다.
해당 문제는 BFS로 풀어야 한다.
내 코드
class Solution:
def orangesRotting(self, grid: list[list[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
time, fresh = 0, 0
queue = deque()
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 2:
queue.append([r,c])
if grid[r][c] == 1:
fresh +=1
directions = [(-1,0), (1,0), (0,-1), (0,1)]
while queue and fresh > 0:
for i in range(len(queue)):
r, c = queue.popleft()
for dr, dc in directions:
row, col = r+dr, c+dc
if row<0 or col<0 or row==ROWS or col==COLS or grid[row][col] != 1:
continue
grid[row][col] = 2
queue.append([row, col])
fresh -=1
time +=1
return time if fresh ==0 else -1
[7]
문제 설명
문제 풀이 방법
내 코드
