[1스4코2파] #133. LeetCode Algorithm Day 9 (542. 01 Matrix, 994. Rotting Oranges)

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코2파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (133일차)
[4코1파] 2023.01.13~ (124일차)
[1스4코1파] 2023.04.12~ (35일차)
[1스4코2파] 2023.05.03 ~ (14일차)

Today :

2023.05.16 [133일차]
LeetCode Algorithm Day 9

542. 01 Matrix
     https://leetcode.com/problems/01-matrix/?envType=study-plan&id=algorithm-i

543. Rotting Oranges
     https://leetcode.com/problems/rotting-oranges/?envType=study-plan&id=algorithm-i

문제 1

[542] 01 Matrix
https://leetcode.com/problems/01-matrix/?envType=study-plan&id=algorithm-i

내 코드

from collections import deque

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        def bfs(mat, visited, queue):
            dx, dy = [1,-1,0,0], [0,0,1,-1]
            while queue:
                qx, qy = queue.popleft()
                for k in range(4):
                    nx, ny = qx+dx[k], qy+dy[k]
                    if 0<=nx<row and 0<=ny<col and visited[nx][ny]==-1:
                        visited[nx][ny] = visited[qx][qy] +1
                        queue.append((nx,ny))

        row, col = len(mat), len(mat[0])
        visited = [[-1]*col for _ in range(row)]
        queue = deque()
        for i in range(row):
            for j in range(col):
                if mat[i][j] == 0:
                    queue.append((i,j))
                    visited[i][j] = 0

        bfs(mat, visited, queue)

        return visited

문제 풀이 방법

이거 DP 래
이 문제는 1에서 가장 가까운 0까지의 거리를 찾는 문제라서,
처음에는 1일 때 0까지의 거리를 구했는데 잘 안구해졌음...
보니까 역으로 0에서 1까지의 거리를 써주는 식으로 사람들이 풀었더라..(ㅎ..)
최소 거리를 구해야 하기 때문에 matrix 에서 9인 인덱스를 queue에 넣고, 빼면서 bfs 를 해 가장 가까운 0이 해당 1에 도달할 때의 distance 값을 구하면 된다... 흑흑

인접 인덱스가 인덱스 범위에 있거나 방문한 적이 없을때,
distance가 초기 값과 같아버리면 queue에 넣고 queue가 빌 때 까지 이를 반복 ㄱ..

증빙

---

문제 2

[994] Rotting Oranges
https://leetcode.com/problems/rotting-oranges/?envType=study-plan&id=algorithm-i

내 코드

from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:

        dx,dy = [1,-1,0,0], [0,0,1,-1]
        row, col = len(grid), len(grid[0])
        fresh, rotten = set(), deque()
        cnt = 0

        for i in range(row):
            for j in range(col):
                if grid[i][j]==1:
                    fresh.add((i,j))
                if grid[i][j]==2:
                    rotten.append((i,j,cnt))

        while rotten:
            qx, qy, cnt = rotten.popleft()
            for k in range(4):
                nx, ny = qx+dx[k], qy+dy[k]
                if 0<=nx<row and 0<=ny<col and grid[nx][ny]==1:
                    grid[nx][ny]=2
                    fresh.remove((nx,ny))
                    rotten.append((nx,ny,cnt+1))

        return cnt if not fresh else -1

문제 풀이 방법

주어진 n X m의 배열(grid)은 빈공간 0, 신선한 오렌지 1, 썩은 오렌지 2로 구성되어 있고, 상한 오렌지에 인접한 신선한 오렌지는 1분이 지날 때마다 상하는데,
인접한 오렌지 중 상한 오렌지가 존재하지 않으면 오랜지는 상하지 않음
모든 오렌지가 상한다면, 그 상할 때까지의 최소 시간을 반환하고,
신선한 오렌지가 1개라도 존재하면 -1을 반환하면 되는 문제..
그래.. 나왔다 또 bfs

증빙

여담

시작됐다 bfs, dfs 지옥