그래프

프로그래밍에서 그래프는 크게 2가지로 표현 가능하다.

1. 인접 행렬 : 2차원 배열로 그래프의 연결 관계 표현. 모든 관계를 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비. 특정 두 노드가 연결되어 있는지 체크할 때는 속도가 빠름

graph = [
	[0, 7, 5],
    [7, 0, INF]
]

2. 인접 리스트 : 리스트로 그래프의 연결 관계 표현. 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용. 다만 두 노드가 연결되어 있는지 체크할 때는 연결된 데이터를 하나하나 체크해야 해서 느리다.

graph = [[] for _ in range(node)]
graph[x].append(y)
graph[y].append(x)

DFS

DFS (Depth-First Search), 깊이 우선 탐색이라고도 부른다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 스택 자료구조를 사용한다. 재귀함수를 통해 구현했을 때 매우 간결하게 구현이 가능하다.

DFS 동작 방식

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다

(방문 처리는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않도록 체크해주는 것. 모든 노드가 한번씩만 처리되도록 보장)

DFS 코드

• 인접 리스트 방식

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=" ")

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]

visited = [False] * 9

dfs(graph, 1, visited)

• 인접 행렬 방식

matrix = [ [0] * (n+1) for _ in range(n+1)]
matrix[a][b] = matrix[b][a]

def dfs(matrix, v, visited):
    visited[v] = True
    for i in range(len(matrix[v])):
        if matrix[v][i] == 1 and not visited[i]:
            dfs(matrix, i, visited)

BFS

BFS (Breadth First Search), 너비 우선 탐색이라고도 부른다. 가까운 노드부터 탐색하는 알고리즘. 큐 자료구조를 사용하며 인접한 노드를 반복적으로 큐에 넣도록 하여 가까운 노드부터 탐색한다.

BFS 동작 방식

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번 과정을 더이상 수행할 수 없을 때까지 반복한다.

BFS 코드

• 인접 리스트 방식

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=" ")
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]

visited = [False] * 9

bfs(graph, 1, visited)

• 인접 행렬 방식

from collections import deque
graph2 = [
    [1, 1, 1, 1, 0, 0],
    [1, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 1],
    [1, 0, 0, 1, 1, 0],
    [0, 0, 0, 1, 1, 0],
    [0, 0, 1, 0, 0, 1],
]


def bfsM(graph, start):
    visited = [False] * len(graph)
    answer = []

    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        answer.append(v)
        for i in range(len(graph[v])):
            if graph[v][i] == 1 and not visited[i] and v != i:
                queue.append(i)
                visited[i] = True
    return answer


print(bfsM(graph2, 0))

프로그래머스 고득점 kit

Lv 2. 타켓 넘버

DFS로 풀었다. 합계를 재귀함수로 같이 넘겨줘야 데이터가 안 꼬임!!!!
나는 계속 지역변수, 배열로 갖고 있어서 헤맸다. 아쉬워~!!
+인 경우에서 쭉 진행하고 -인 경우에서 쭉 진행하므로 DFS로 풀었다. 물론 BFS로 풀 수도 있을듯?

def solution(numbers, target):
    answer = 0
    
    def dfs(idx, result):
        nonlocal answer
        
        if idx == len(numbers):
            if result == target:
                answer += 1
            return 
        
        dfs(idx+1, result + numbers[idx])
        dfs(idx+1, result - numbers[idx])
    
    dfs(0, 0)
        
    return answer

Lv 3. 네크워크

앞 문제는 DFS로 풀었으니 이번 문제는 BFS로 풀어보았다. 그래프가 총 몇개 있는지 체크해주면 되는 간단한 문제였다. 방문 처리를 하는 visit 배열을 돌면서 bfs를 총 몇번 돌았는지가 그래프의 개수이다!

큐에 넣을 때 방문처리해주고 넣는거 잊지말자!

from collections import deque
def solution(n, computers):
    answer = 0
    
    visit = [False] * (n)
    
    graph = [ [] for _ in range(n) ]
    
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            if computers[i][j] == 1:
                graph[i].append(j)
    
    def bfs(start):
        q = deque([start])
        visit[start] = True
        while q:
            now = q.popleft()
            for node in graph[now]:
                if not visit[node]:
                    q.append(node)
                    visit[node] = True
    
    
    for i in range(len(visit)):
        if not visit[i]:
            bfs(i)
            answer += 1
        
    return answer

Lv 2. 게임 맵 최단거리

그래프를 BFS로 돌면서 최단거리를 체크해주면 된다. 간단한 문제였다! graph의 좌표값을 더해가면서 만약 최종적인 위치((n,m))의 값이 1인 경우는 도달하지 못한 것이므로 return -1을, 아니면 위치값을 리턴해주면 된다.

이 문제의 경우 1인 경우에만 방문하면 되므로 방문처리 배열이 따로 필요 없다 :)

from collections import deque
def solution(maps):
    answer = 0
    
    N = len(maps) # 행 row
    M = len(maps[0]) # 열 col
    
    dx = [-1, 1, 0, 0] # 상 하 좌 우
    dy = [0, 0, -1, 1]
    
    q = deque([(0,0)])
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dx[i]
            nc = c + dy[i]
            
            if 0 <= nr < N and 0 <= nc < M:
                if maps[nr][nc] == 1:
                    maps[nr][nc] = maps[r][c] + 1
                    q.append((nr, nc))
    
    if maps[N-1][M-1] == 1:
        return -1
    else:
        return maps[N-1][M-1]

Lv 3. 단어 변환

begin 단어에서 target 단어로 변경 가능한 최소 횟수를 찾는 것이므로 BFS 방식을 사용했다. 한번에 글자는 한개씩만 바꿀 수 있기 때문에 한 글자만 다른 경우에 참을 리턴하는 checkDiff()함수를 만들었다.

words 배열을 돌면서 큐에 (변경 가능한 글자, 바꾼횟수) 를 넣어주었다.
만약 바꾼 횟수가 words 배열보다 길어지면 그 경우는 더이상 볼 필요가 없기 때문에 넘어갔고 target과 같아지는 경우 반복을 그만뒀다. (BFS로 돌기 때문에 바로 멈춰도 OK)

from collections import deque

def checkDiff(w1, w2):
    count = 0
    for i in range(len(w1)):
        if w1[i] != w2[i]:
            count += 1
    if count == 1:
        return True
    else:
        return False
        
def solution(begin, target, words):
    if not target in words:
        return 0
    
    q = deque([(begin, 0)])
    while q:
        w, count = q.popleft()
        
        if w == target:
            break
            
        # 이 경우의 수는 볼 필요 없음
        if count > len(words): 
            continue
            
        for word in words:
            if checkDiff(w, word):
                q.append((word, count+1))
        
    answer = count
    return answer

Lv 3. 여행경로

계속해서 테스트케이스 1번에서 통과하지 못했다. 현재 내 코드에서는 중복 티켓까지는 처리가 된다. 다만 도착지 기준으로 오름차순 정렬을 해놓아 만약 해당 티켓을 뽑았을 때 올바르지 않은 경로면 그냥 끝나버린다.
코드는 다음과 같다 엉엉

from collections import deque

def solution(tickets):
    answer = []
    
    airports = sorted(set(([i[0] for i in tickets])))
    
    graph = [ [] for _ in range(len(airports))] # airports의 인덱스와 graph의 인덱스 동일하게 맞추기
    
    for dep, arr in tickets:
        graph[airports.index(dep)].append(arr)
    
    for i in range(len(airports)):
        graph[i].sort()
    
    print(airports)
    print(graph)
    
    count = 1
    q = deque([airports.index("ICN")])
    answer.append("ICN")
    while q:
        dep = q.popleft()
        for arr in graph[dep]:
            if arr not in airports and count == len(tickets):
                answer.append(arr)
                break
            if arr not in airports:
                continue
            
            if count != len(tickets) and len(graph[airports.index(arr)]) == 0:
                continue
                
            q.append(airports.index(arr))
            answer.append(arr)
            count += 1
            graph[dep].remove(arr)
            break
    return answer

도저히 어떻게 경로를 다시 넣는지 모르겠어서 구글링을 했다.
다들 DFS로 많이 풀었다... 좋아보이는 코드 (출처)가 있어서 가져왔다.

from collections import defaultdict

def solution(tickets):
    t_dict = defaultdict(list)
    
    # key: 출발지, value: 목적지인 딕셔너리 (키 값이 없는 경우 자동 생성을 위해 defaultdict 사용)
    for s, e in tickets:
        t_dict[s].append(e)
    
    # 목적지 기준 내림차순 정렬 (따로 deque를 사용하지 않기 위해!!) (pop()하면 알파벳 순서 상 가장 빠른 티켓이 뽑힌다)
    for t_key in t_dict.keys():
        t_dict[t_key].sort(reverse = True)
    
    answer = []
    path = ["ICN"]
    
    # DFS를 실행. 처음에는 맨 마지막 공항까지 쭉쭉 나아감.
    # 어느 순간 다른 공항으로 가는 티켓도 없고, 또는 그런 티켓을 다 소진한 어떤 공항에 도착한다면 그 곳이 맨 마지막에 도달하게 될 공항.
    # 이제 path에서 pop해서 하나씩 answer에 넣어줌으로써 path를 역방향으로 거슬러 올라감
    # 다만 맨 마지막 공항에 처음으로 도착했을 때의 path가 모든 간선을 다 사용하지 않은 path일 수도 있음.
    # 그러므로, 한 칸씩 내려가면서 그 공항과 연결된 인접 공항들을 싹 다 돌아주면 됨. (else 부분)
    # 이렇게 ICN까지 쭉 실행해주면 path는 비게 되고 answer에는 역방향의 정답 루트가 담겨있게 됨.
    while path:
        now = path[-1]
        
        if now not in t_dict or len(t_dict[now]) == 0:
            answer.append(path.pop())
        else:
            path.append(t_dict[now].pop())
    
    return answer[::-1]

Lv 3. 아이템 줍기

오기로 2시간 꼬박 걸려서 풀었는데... 과연 실제로 코테에 나왔어도 풀 수 있었을까 싶어서 조금 슬퍼진 문제. 어쨌거나 2시간 걸려서 풀긴 풀었다!!!! 크악

문제를 풀려면 몇 가지 포인트가 필요하다.

1. 겹쳐진 직사각형의 테두리만 살려야 한다 -> 즉, 테두리만 1로 냅두고 내부는 0으로 바꿔줘야 한다. drawRect(), eraseRect() 함수로 구현했다.
2. 핵심 포인트인데, 테케 1번에서 계속 에러가 난 이유였다. 좌표값을 그대로 사용하면 잘못된 값이 들어갈 수 있다
   그림을 보면 이해할 수 있다.
   

보면 빨간색으로 표시된 좌표가 (3,5)이다. 그래프 기준 상하좌우를 보면서 값이 1인 경우 방문 가능한 좌표로 보고 큐에 넣는데 문제 의도대로라면 오른쪽 (4,5)으로만 이동할 수 있어야 한다. 그러나 (3,6) 역시 유효한 직사각형의 테두리이기 때문에 큐에 값이 들어가 버린다!!
즉, 좌표를 벌려줘야 한다. 따라서 기존 코드에서 좌표값만 싹 다 x2해주고 최종 결과값을 //2 해줘서 통과했다!!!!

코드는 다음과 같다.

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    
    graph = [ [0]* 102 for _ in range(102)]
    
    # 사각형 기준 그래프 그리기
    def drawRect(LBx, LBy, RTx, RTy):
        for x in range(LBx, RTx + 1):
            graph[x][LBy] = 1
            graph[x][RTy] = 1
            
        for y in range(LBy, RTy+1):
            graph[LBx][y] = 1
            graph[RTx][y] = 1    
    
    # 내부 선 지우기
    def eraseInner(LBx, LBy, RTx, RTy):
        for x in range((LBx+1), RTx):
            for y in range((LBy+1), RTy):
                graph[x][y] = 0
    
    for LBx, LBy, RTx, RTy in rectangle:
        drawRect(LBx*2, LBy*2, RTx*2, RTy*2)
        
    for LBx, LBy, RTx, RTy in rectangle:
        eraseInner(LBx*2, LBy*2, RTx*2, RTy*2)
    
    
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 좌 우 하 상
    
    def bfs(startX, startY):
        q = deque([(startX, startY)])
        
        while q:
            x, y = q.popleft()
            
            for i in range(4):
                nx = x + move[i][0]
                ny = y + move[i][1]
            
                if (1 <= nx <= 102 and 1 <= ny <= 102) and graph[nx][ny] == 1:
                    if nx == startX and ny == startY:
                        continue
                    graph[nx][ny] = graph[x][y] + 1
                    q.append((nx, ny))
    
    bfs(characterX*2, characterY*2)

    answer = graph[itemX*2][itemY*2] // 2
    return answer

위의 코드에서 if nx == startX and ny == startY: continue 이 부분은 시작좌표가 다시 큐에 들어가버려서 추가했다. (따로 방문좌표를 저장하는 배열을 쓰지 않고 이렇게 해결했다)

Lv 3. 퍼즐 조각 채우기

하... 2시간정도 투자하면 풀릴 줄 알고 열심히 헤딩했는데 잘 안되어서 코드를 일단 첨부한다 ㅠㅠ 어디서 막혔는지 알겠어서 더 답답하다!!!

코드가 엄청 긴데... 일단 블록을 회전시킬 수 있다 했으니 가능한 블록의 회전 시나리오를 모두 저장했다. 이때 어느 좌표에서 이동한 건지 체크할 수 있도록 count 변수를 추가했다. 테트리스 ㅗ 모양 때문이다. (하필 모양도 ㅗ다....)

테스트케이스까지는 다 통과하는데 도대체 어디서 막히는지 알수가 없다...!!!

from collections import deque
from collections import defaultdict
# 90도 회전 Right -> Bottom -> Left -> Top 순서로 변경됨
def solution(game_board, table):
    answer = 0
    
    # 블록 모양 
    move = [(-1, 0), (0, 1), (1, 0), (0, -1)] # T, R, B, L (시계방향)

    def tableBfs(startX, startY):
        result = [[], [], [], []]
        temp = []
        q = deque([(startX, startY)])
        count = 0
        while q:
            x, y = q.popleft()
            count += 1
            table[x][y] = 0
            for i in range(4):
                nx = x + move[i][0]
                ny = y + move[i][1]
                if 0 <= nx < len(table) and 0 <= ny < len(table):
                    if table[nx][ny] == 1:
                        temp.append(str(i) + str(count))
                        table[nx][ny] = 0
                        q.append((nx, ny))
        
        # 회전한 시나리오까지 전부 포함                
        for item in temp:
            move_dir = int(item[0])
            for i in range(4):
                result[i].append(((move_dir + i) % 4, int(item[1])))
            
        return result
    
    blocks = [] # 가능한 블록 시나리오
    blocks_count = [] # 각 블록 인덱스가 몇칸짜리 블록인지 
    for i in range(len(table)):
        for j in range(len(table)):
            if table[i][j] == 1:
                blocks.append(tableBfs(i,j))
                blocks_count.append(len(blocks[-1][-1])+1)
    
    # game_board 방문 좌표 저장용
    visit = [ [False]*len(game_board) for _ in range(len(game_board))]
    def game_boardBfs(startX, startY):
        pos = [(startX, startY)] # 빈칸의 좌표값들 저장
        
        q = deque([(startX, startY)])
        visit[startX][startY] = True
        
        while q:
            x, y = q.popleft()
            
            for i in range(4):
                nx = x + move[i][0]
                ny = y + move[i][1]
                if 0 <= nx < len(game_board) and 0 <= ny < len(game_board):
                    if game_board[nx][ny] == 0 and not visit[nx][ny]:
                        visit[nx][ny] = True
                        q.append((nx, ny))
                        pos.append((nx, ny))
        return pos
    
    zeros = [] # game_boards 빈칸 좌표 저장
    zeros_count = []
    for i in range(len(game_board)):
        for j in range(len(game_board)):
            if game_board[i][j] == 0 and not visit[i][j]:
                zeros.append(game_boardBfs(i,j))
                zeros_count.append(len(zeros[-1]))
    
    
    
    def isFill(x, y, blockArr):
        position = {}
        
        for move_idx, pos in blockArr:
            if pos not in position:
                position[pos] = (x, y)
            if pos == 1:
                x += move[move_idx][0]
                y += move[move_idx][1]
            else:
                x = position[pos][0] + move[move_idx][0]
                y = position[pos][1] + move[move_idx][1]
            
            if 0 <= x < len(game_board) and 0 <= y < len(game_board):
                if game_board[x][y] != 0:
                    return False
            else:
                return False
            
        return True
    
    
    # 빈칸 돌면서 채울 수 있나 보기
    for i in range(len(zeros)):
        check = []
        for idx, val in enumerate(blocks_count):
            if zeros_count[i] == val:
                check.append(idx)
                
        # check 배열에 들어가있는 blocks 돌면서 보면 됨
        flag = False
        for check_block_idx in check:
            if flag:
                break
            for j in range(len(zeros[i])):
                if flag:
                    break
                for rotate_idx in range(4):
                    flag = isFill(zeros[i][j][0], zeros[i][j][1], blocks[check_block_idx][rotate_idx])
                    if flag:
                        answer += zeros_count[i]
                        break
        if flag:
            blocks_count[check_block_idx] = 0
            
    return answer

내 코드를 사용하고 싶어서 상대적인 좌표값도 넣어보고 이것저것 시도를 많이 했는데 이전 데이터를 기반으로 움직이게 하는 걸 회전시키는게 여의치가 않다. 사실 LRTB 값만 갖고 있으면 안되고, 어느 좌표를 기준으로 움직였는지도 갖고 있어야 하는데 그게 여의치가 않다.

구글링을 해보니까 사각형으로 만들어서 회전을 시키던데 그게 훨씬 괜찮아보였다. 실제로 코테에서 만약 이런 난이도와 빡센 구현정도로 나온다면 핵심 기능별로 다 쪼개서 부분부분 구현해야겠다. tableBFS() 함수는 살려두고 내부를 고치는 등...