99클럽 TIL (240822)

> [Middler] 무인도 여행

https://school.programmers.co.kr/learn/courses/30/lessons/154540

 

문제 풀이 과정

같은 무인도끼리 머물 수 있는 일자를 구해주면 된다. DFS로 문제를 해결했다.

문제를 풀면서 어려웠던 점은 주어지는 maps 요소들이 문자열이라는 점이었다. 문자열의 특정 인덱스 값만 변경하려고 하다보니 에러가 발생해서 우선 maps를 2차원 배열로 만들어 주었다.

 

1. maps를 돌면서 'X' 가 아니고 방문한적 없다면 무인도이므로 식량의 개수를 센다.

2. 현재 위치에서 상,하,좌,우로 DFS를 돌려 하나의 무인도에서 발견할 수 있는 식량의 개수를 모두 합하고 정답 배열에 append한다.

3. 만일 지낼 수 있는 무인도가 없다면 -1을 담아 리턴한다.

 

문제 풀이

python

def solution(maps):
    maps = [list(m) for m in maps]
    q = []
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    res = []
    # dfs
    for i in range(len(maps)) :
        for j in range(len(maps[0])) :
            if maps[i][j] != 'X' and maps[i][j] != '0' :
                q.append([i,j])
                food = 0
                
                while q :
                    x,y = q.pop()
                    food += int(maps[x][y])
                    maps[x][y] = '0' #식량 다 사용
                    
                    for k in range(4) :
                        nx = x + dx[k]
                        ny = y + dy[k]
                        
                        if nx < 0 or ny < 0 or nx >= len(maps) or ny >= len(maps[0]) : continue
                        if maps[nx][ny] == 'X' or maps[nx][ny] == '0' : continue
                        
                        q.append([nx, ny])
                
                if food > 0 :
                    res.append(food)
    if len(res) == 0 :
        return [-1]
    else :
        return sorted(res)

시간복잡도 O(N)

maps, maps[0] <= 100 이므로 이중반복임에도 시간초과가 발생하지 않는다.

 

회고 및 느낀점

DFS 문제는 연습!

---

> [Challenger] 아이템 줍기

https://school.programmers.co.kr/learn/courses/30/lessons/87694

 

🔥 다시풀기 🔥

 

문제 풀이 과정

우선 문제를 처음 봤을 때, 풀이가 떠오르진 않았다. 직사각형 예시들을 보면서 풀이를 생각해봤는데 처음 생각은 이랬다.

• rectangle 배열을 돌면서 캐릭터의 x,y 좌표값이 해당 직사각형에 존재한다면 연산을 해줘야하는 것 아닌가..?

하지만 아무리 생각해봐도 어떤 규칙성이나 이를 코드로 구현하는 방법이 생각나지 않았다. 그래서 소스를 보고 이해했다. 소스를 보고 이해한 바를 기록한다..ㅠ

 

동작 과정

1. 위의 직사각형들을 2차원 리스트로 생각한다. 선이 지나가는 부분이 1, 사각형 내부는 0, 외부는 -1 으로 채운다.

2. BFS로 최단 거리를 찾는다.

 

주의해야할 부분

위의 경우에서 BFS를 돌릴 때, 왼쪽의 올바른 경로로 가지 않고 틀린 경로로 갈 수 있다. 현재 좌표값을 보고 탐색하기 때문에 (3,5)가 (3,6)랑 바로 연결되어 있는지, (3,5) -> (4,5) -> (4,6) -> (3,6) 으로 연결되어 있는지 알 수 없다. 

 

그래서 맵 크기를 2배로 확장하면 정확히 검색해줄 수 있다. 2배로 확장하게 되면 연결되어 있지 않은 좌표를 구분할 수 있기 때문!

로직 순서

1. graph (=직사각형 2차원리스트) 와 visited (=거리 메모리스트)를 초기화한다.

2. rectangle 테두리에 해당하면 1, rectangle내부는 0 외부는 -1로 graph를 설정한다.

  * 이 때, 좌표값들을 2배해서 계산한다.

3. 캐릭터 좌표값과 아이템 좌표값을 2배해준다.

4. BFS를 돌린다. 캐릭터위 위치값이 아이템의 위치값이 되면 visited를 리턴한다.

 

문제 풀이

python

from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    # (내생각) 직사각형의 좌표값은 최대 50개, 2배하면 100개, x축 y축 0포함해야 함으로 +2
    graph = [[-1 for _ in range(102)] for _ in range(102)]
    visited = [[1 for _ in range(102)] for _ in range(102)]
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    
    for r in rectangle :
        sx, sy, ex, ey = map(lambda x : x*2, r)
        for i in range(sx, ex+1) :
            for j in range(sy, ey+1) :
                if sx < i < ex and sy < j < ey :
                    graph[i][j] = 0
                # 다른 직사각형의 내부가 아니면서 테두리일 때 1로 채움
                elif graph[i][j] != 0 :
                    graph[i][j] = 1
    
    #아이템, 캐릭터 좌표 2개
    cx, cy, ix, iy = characterX*2, characterY*2, itemX*2, itemY*2
    
    q = deque()
    q.append((cx, cy))
    while q :
        x, y = q.popleft()
        
        if x == ix and y == iy :
            answer = visited[x][y] // 2
            break
        
        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]
            
            if graph[nx][ny] == 1 and visited[nx][ny] == 1 :
                visited[nx][ny] += visited[x][y]
                q.append((nx,ny))
    
    return answer

 

시간복잡도 O(V+E)

 

회고 및 느낀점

문제를 푸는 아이디어를 많이 많이 겟하자