[TIL_Carrotww] 102 - 23/02/23

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 programmers 미로탈출 level2

전형적인 bfs 문제이다

• 내 풀이

def solution(maps):
    from collections import deque
    dx, dy = [1, -1, 0, 0], [0, 0, -1, 1]

    queue1 = deque()
    queue2 = deque()

    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == 'S':
                start_node = (i, j, 0)
            elif maps[i][j] == 'L':
                lever_node = (i, j, 0)

    def bfs(path, end_node):
        cnt = 0
        visited = [[0 for _ in range(len(maps[0]))] for _ in range(len(maps))]
        visited[path[0][0]][path[0][1]] = 1

        while path:
            x, y, cnt = path.popleft()
            for i in range(4):
                n_x, n_y = dx[i] + x, dy[i] + y
                if (n_x >= 0 and n_x < len(maps)) and (n_y >= 0 and n_y < len(maps[0])):
                if maps[n_x][n_y] == end_node:
                    return cnt + 1
                elif not maps[n_x][n_y] == 'X' and visited[n_x][n_y] == 0:
                    path.append((n_x, n_y, cnt + 1))
                    visited[n_x][n_y] = 1
    return -1

queue1.append(start_node)
queue2.append(lever_node)
to_L = bfs(queue1, 'L')
to_E = bfs(queue2, 'E')

if to_L == -1 or to_E == -1:
    return -1
return to_L + to_E

레버까지의 가는 길, 그리고 레버에서 종료지점까지 가는 길을 bfs로 돌리면 된다
처음에 X 가 아닌 길 일때 path에 append 하라는 부분을 O 일때 가라고 코드를 짜서 테스트 케이스 2개가 틀렸었다.
벽 빼고 레버와 종료지점은 갈 수 있어야 되기 때문에 위와같이 작성해주어야 한다.

🧲 python algorithm

🔍 programmers 단어 변환 level2

이 문제도 전형적인 bfs 문제이다.

• 풀이

def solution(begin, target, words):
    from collections import deque
    queue = deque([(begin, 0)])
    result = 0
    visited = [0 for _ in range(len(words))]

    while queue:
        cur_word, cnt = queue.popleft()
        if cur_word == target:
            return cnt
        for i in range(len(words)):
            temp_cnt = 0
            for j in range(len(words[i])):
                if cur_word[j] != words[i][j]:
                    temp_cnt += 1
            if temp_cnt == 1 and visited[i] == 0:
                visited[i] = 1
                queue.append((words[i], cnt + 1))

    return result

문자열을 하나씩 비교하는게 맞나 싶었지만 그냥 비교하면 된다.
문제에 단어 길이도 길지 않고 총 words list의 길이도 짧기 때문이다.

🧲 python algorithm

🔍 programmers 네트워크 level2

이 문제는 dfs로 풀었다.

• 풀이

def solution(n, computers):
    from collections import defaultdict
    result = 0
    stack = []
    visited = [0 for _ in range(n)]
    path = defaultdict(list)
    for i in range(len(computers)):
        for j in range(len(computers[i])):
            if computers[i][j] == 1:
                path[i].append(j)

    for i in range(n):
        if visited[i] == 1:
            continue
        stack.append(i)
        while stack:
            node = stack.pop()
            for n_node in path[node]:
                if visited[n_node] == 1:
                    continue
                stack.append(n_node)
                visited[n_node] = 1
        result += 1

    return result

path 를 defaultdict로 선언하고 자기 자신에게 가는 경로도 포함을 해서 path에 자기 자신을 포함한 다음 노드로 갈 수 있는 지도를 만든다.

그리고 전체 노드를 하나 씩 돌며 visited 값이 0인
즉) 방문하지 않았던 노드에 들어가서 연결되어 있는 곳들을 모두 방문한다.
bfs, dfs 뭘로 하여도 상관없다.
방문한 곳은 visited에 다 추가해주고 while문을 돌때만 result를 더해준다.