99클럽 TIL (240823)

> [Middler] 리코쳇 로봇

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

 

문제 풀이 과정

한 방향으로 계속 이동한 뒤 장애물을 마주쳤을 때, 이동을 멈춘다. 이런 경우 목표지점에 도착하는 최소 이동거리를 구하라.

 

알아야하는 점

처음에 DFS로 생각한 이유는 좌표를 이동할 때 벽을 만날때까지 이동한다면 스택을 이용하는 게 맞지 않나라는 생각이 들어서 DFS를 생각했다. 찾아보니 코테문제 풀 때 보통 아래처럼 DFS/BFS 사용하는 경우가 많다고 하니 참고하자. 

• DFS : 완전탐색
• BFS : 최단거리

이 문제 풀이는 DFS/BFS 둘다 가능하지만, base condition을 통해 시간초과나지 않게 구현하는 것이 중요했던 것 같다. 그 조건을 거는 부분을 해결하지 못해서 참고했다.

 

로직 동작 과정

1. dist 거리 리스트를 초기화

2. board 2차원 리스트에서 로봇이 위치한 좌표에서 BFS를 돌린다.

3. 큐를 초기화하고 큐에 원소와 움직임(length)를 넣는다.

4-1. 큐에 원소가 있을 때까지 popleft() 한다.

4-2. 상하좌우를 확인하는데, 이동한 거리가 board 를 벗어나지 않고 장애물(D)가 아닐때까지 이동시킨다. (=미끄러진다) 장애물을 만나면 dist[nx][ny] 와 움직임+1 을 비교해 현재 움직임이 더 적은 경우에 기록하고 큐에 넣는다.

 * 만약 어떤 과정을 거쳐서 움직이다가 거리를 비교해보니 저장된 값보다 현재 움직임이 더 크다면 갈 필요가 없기 때문이다.

5. 4의 과정을 반복한다.

 

 

문제 풀이

python

from collections import deque
def solution(board):
    # 미끄러지는 움직임은 장애물이나 맨 끝에 부딪힐때까지 움직인다. -> BFS
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    q = []
    dist = [[float('inf') for _ in range(len(board[0]))] for _ in range(len(board))]
    def bfs(i,j, num) :
        ans = 0
        q = deque([])
        q.append((i,j,num))
        while q :
            x,y, length = q.popleft()
            if board[x][y] == "G" :
                return length
            for d in range(4):
                nx = x 
                ny = y 
                while 0 <= nx+dx[d] < len(board) and 0 <= ny+dy[d] < len(board[0]) and board[nx+dx[d]][ny+dy[d]] != "D" :
                    nx += dx[d]
                    ny += dy[d]
                # 이부분 생각하지 못함 - 집즁
                if dist[nx][ny] > length + 1 :
                    dist[nx][ny] = length+1
                    q.append((nx,ny,length+1))
        return -1
                        
    for i, b in enumerate(board) :
        for j, v in enumerate(board[0]) :
            if board[i][j] == "R" :
                return bfs(i,j,0)

시간복잡도 O(N+E)

 

회고 및 느낀점

BFS, DFS 는 반복을 탈출하는 조건을 잘 작성해야 한다. 이 문제에서 현재 이동한 거리와 기록된 거리를 비교한다는 개념을 가져가자.

 

---

> [Challenger] 단어 변환

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

 

🔥다시보기🔥

문제 풀이 과정

BFS로 풀어서 최단 거리를 찾아야겠다고 생각했으나, 2차원리스트가 아닌 곳에서의 구현이 잘 생각나지 않았다.

1. 큐에 (0, begin) 을 넣는다.

2. words와 비교한다.

위의 동작까지는 생각했지만, 문제에 나와있는 조건 한번에 한 알파벳만 변경, words에 존재하는 단어로만 변경할 수 있다를 구현하는 것이 생각나지 않아 코드를 참조했다.

 

동작 과정

1. words 길이만큼 방문 기록 테이블을 초기화한다.

2. 큐에 시작 단어와 거리를 넣는다.

3. 큐를 popleft 하고 해당 노드에 방문하지 않았다면 words를 확인하며 word와 현재 단어의 알파벳이 다르면 change + 1 해준다.

4. change가 1인 경우에는 문제 조건대로 하나의 알파벳을 변경하여 words 에 존재하는 단어로 변경한 것이기 때문에 현재 단어와 거리+1 한 값을 큐에 넣는다.

5. 큐가 빌때까지 반복하고 현재 단어가 target과 동일하다면 거리를 반환한다.

 

문제 풀이

python

from collections import deque
def solution(begin, target, words):
    visited = [ False for _ in range(len(words)) ]
    q = deque()
    q.append((0, begin))
    ans = 0
    while q :
        cnt, word = q.popleft()
        if word == target :
            ans = cnt
            break
        for i in range(len(words)) :
            change = 0 
            if not visited[i] :
                for j in range(len(word)) :
                    if word[j] != words[i][j] :
                        change += 1
                if change == 1 :
                    q.append((cnt+1, words[i]))
                    visited[i] = 1
    return ans

시간복잡도 O(V+E)

회고 및 느낀점

좌표값이 주어지는 문제가 아닐 때의 DFS/BFS 도 많이 풀어보자. 큐에 넣고 방문처리를 하는 로직은 비슷하다!