파이썬 - graph 실전 문제

목차

-시작
-문제 1
-문제 2
-문제 3
-문제 4
-백준에서 풀어보면 좋은 문제들

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

코딩테스트 연습

 

시작

이번 시간에는 기본 graph 알고리즘 지식을 바탕으로 실전 문제를 풀어볼 것입니다.
실전 문제에서는 2차원 행렬이 주어질 때 회전과 방향을 고려하여 해결하는 문제가 대부분입니다.

실전 문제는 프로그래머스와 백준의 문제를 사용하고 있습니다.
문제의 생각 흐름을 보기 전 먼저 해당 사이트에 접속해 문제를 푸는 것을 추천드립니다.

그러면 바로 문제로 들어가 봅시다.

문제 1 : 행렬의 회전 다루기 - 행렬 테두리 회전하기

https://programmers.co.kr/learn/courses/30/lessons/77485

코딩테스트 연습 - 행렬 테두리 회전하기

문제는 대략 이렇습니다.
1. 2차원 평면과 2점들을 담은 리스트가 주어집니다.
(2차원 평면은 rows*colums이고 성분으로 rows*columns를 가지고 있습니다.)
2. 리스트의 성분마다 직사각형을 만들 수 있습니다.
3. 이 직사각형의 테투리를 시계방향으로 회전시킵니다.
4. 결과를 취합하여 답을 제출합니다.

문제를 읽고 드는 생각
이 문제는 명확한 구현 방식이 문제에 제공이 되어 있습니다.
특히 matrix에서 테두리 회전만 잘 구현하면 쉽게 정답 판정을 받을 수 있습니다.

의사 코드 작성

1. 2차원 평면을 만든다. 성분은 rows*columns이고, 크기는 rows*columns
2. queries를 loop를 돌며 직사각형의 테두리 조사한다.
3. 직사각형의 테두리를 4 부분으로 나누어 deque 자료구조에 넣는다.

   시계 방향으로 회전시키기 위해 deque.rotate(1)을 진행한다.

   deque.popleft를 이용하여 직사각형의 성분을 변경한다.

구현

from collections import deque
def solution(rows, columns, queries):
    m = [ [columns*j + i for i in range(1,columns+1)] for j in range(rows)]
    answer = []
    for q in queries:
        rotate(m, q, answer)
    return answer

def rotate(m,q,answer):
    x1, y1, x2, y2 = q[0] -1, q[1] -1, q[2] -1, q[3] -1
    dum = deque()
    idx = 0
    for up in range(y1, y2):
        dum.append(m[x1][up])
    for right in range(x1, x2):
        dum.append(m[right][y2])
    for down in range(y2, y1, -1):
        dum.append(m[x2][down]) 
    for left in range(x2, x1, -1):
        dum.append(m[left][y1])  
    answer.append(min(dum))
    dum.rotate(1)
    
    for up in range(y1, y2):
        m[x1][up] =  dum.popleft()
    for right in range(x1, x2):
        m[right][y2] =  dum.popleft()
    for down in range(y2, y1, -1):
        m[x2][down] = dum.popleft()
    for left in range(x2, x1, -1):
        m[left][y1] = dum.popleft()

 

문제 2 : 카카오 행렬 회전 문제 - 자물쇠와 열쇠

https://programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

문제는 대략 이렇습니다.
key를 나타내는 행렬과 lock을 나타내는 행렬이 있습니다.
key를 이동과 회전을 이용하여 lock을 열 수 있는지 아닌지 확인하는 문제입니다.

문제를 읽고 드는 생각
이전 문제에서 회전 구하는 거 너무 힘들고 지친 일이었습니다.
또해? 내 또 해야 합니다.
회전을 다루는 문제의 경우 문제는 trival하나 구현이 힘든 게 특징입니다.
참고 구현까지 해봐야 합니다.
몇 번 하다 보면 자신만의 패턴이 생겨 나중에는 좀 더 수월하게 할 수 있습니다.
좀만 참으면 됩니다.

 

rotate를 어찌하면 쉽게 구현하지?

파이썬의 zip() 함수를 이용하면 쉽게 구현할 수 있습니다.

아래의 예를 봅시다.

test = [
["a1", "a2", "a3"],
["b1", "b2", "b3"],
["c1", "c2", "c3"],
        ]

#zip(*)를 이용하면 새로로 형성된 결과를 가져옵니다.
for ele in zip(*test):
    print(ele)
    
---> 출력 결과
('a1', 'b1', 'c1')
('a2', 'b2', 'c2')
('a3', 'b3', 'c3')

#출력된 ele를 reverse하여 합치면 90도 회전이 구현됩니다.
result = []
for ele in zip(*test):
    result.append(list(ele[::-1]))

#90도 회전한 행렬의 모습
for ele in result:
    print(ele)
 
---> 출력 결과
['c1', 'b1', 'a1']
['c2', 'b2', 'a2']
['c3', 'b3', 'a3']

의사 코드 작성
1. 90도 회전을 구현합니다.
2. 90도 회전을 3번 진행하며 loop를 수행합니다.
3. 90도로 n번 회전한 key를 2중 for loop를 이용하여
   lock과 잘 맞는지 확인합니다.

   편리한 구현을 위해 아래의 그림과 같이 lock을 다시 정의한다.

   그리고 loop마다 copy 하여 사용한다.

   copy 한 lock이 조건에 맞는지 확인하여 정답을 제출한다.

구현

def solution(key, lock):
    n =  len(key)
    m = len(lock)
    lock = [["e"]*n + ele + ["e"]*n for ele in lock]
    dum = [["e"]*(2*n +m) for _ in range(n)]
    lock = dum + lock + dum
    for _ in range(4):
        key = rotate(key)
        for x in range(len(lock)-n):
            for y in range(len(lock)-n):
                lock_c =  [ele[:] for ele in lock]
                change(x,y,key,lock_c)
                if ck(lock_c):
                    return True
    return False

def rotate(key):
    result = []
    for ele in zip(*key):
        dum = list(ele)
        result.append(dum[::-1])
    return result

def change(x,y,key,lock_c):
    for x_ in range(x, x+len(key)):
        for y_ in range(y, y+len(key)):
            if lock_c[x_][y_] == "e":
                continue
            lock_c[x_][y_] += key[x_-x][y_-y]
            
def ck(lock):
    for row in lock:
        for ele in row:
            if ele == 0 or ele == 2:
                return False
    return True

 

문제 3: visited 변경을 고려해야 하는 문제 - 경주로 건설

https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

문제는 대략 이렇습니다.
최소 비용을 계산하는 문제입니다.
문제의 인풋으로 0과 1로 구성된 board가 주어집니다.
0은 건설할 수 있는 지역이고 1은 건설 불가 지역입니다.
(0,0)부터 시작하여 (n-1, n-1)까지 가는 경주로를 건설해야 합니다.
직선의 경우 칸당 100원의 비용이 발생하고 코너의 경우 500원이 추가로 발생합니다.

문제를 읽고 드는 생각
배열이 크기가 무진장 작습니다. 25 개꿀
모든 경우를 탐색하는 완전 탐색으로 접근하면 될듯합니다.
이거 코너를 최대학 적게 사용하면 되는 그리디 아니야?라고 생각할 수 있지만
그리드가 25로 무진장 작기 때문에 리스크 있는 일을 할 필요가 없습니다.
그러면 DFS로 해야 하나 BFS 해야 하나?
둘 다 가능할 듯 하지만.
최소 비용을 계산하기 적합한 BFS로 트라이하면 좋을 듯합니다.

 

방문처리
예제 4번을 보면 빨간 경로와 파란 경로가 있습니다.
파란 경로가 실제 거리는 작지만 가격이 저렴합니다.

note 기본적인 BFS라면 한번 방문한 노드는 (x, y)두 변수를 이용하여 방문처리 하면 최소 경로가 보장됩니다.

파란색이 이미 방문 처리가 되어 빨간 경로가 고려가 되지 않습니다.

이로부터 알 수 있는 사실은 BFS의 방문처리 부분을 기존의 것과 동일하게 (x, y)만 이용해서는 처리가 되지 않는 것을 알 수 있습니다.

문제를 해결하기 위해서는 BFS의 방문 처리 부분을 수정해야 합니다.

그러면 어떻게 수정하면 좋을까요?

방문처리를 진행할 때 코너수까지 고려하면 어떨까요?

(x, y, 코너수 = k)로 방문처리를 하게 되면  x, y좌표에 코너수가 1개 일 때부터 k까지 사용할 때 갈 수 있는 최단경로를 얻을 것입니다.

 

건설비용 계산

건설 비용은 방향을 고려하여 계산하여야 합니다.

그러니 기존에 BFS에서 큐에 append 할 때 또는 다음 노드로 넘겨줄 때 방향을 같이 넘겨줘야 합니다.

직전 노드에 대하여 방향이 변하면 +600, 방향이 같으면 +100를 해야 합니다.

의사 코드 작성

1. 초기 조건을 설정한다. 0,0에서 오른쪽 방향과 아래쪽 방향이 가능하다.

2. vitited를 {}로 초기화한다. 처리할 다음 노드를 ns = [start]로 지정한다.

3. ns에 대하여 loop를 돈다. ns의 모든 노드에 대해  visited에 {(x, y, k) : cost } 형식으로 추가한다.

4. 코너의 수를 고려한 adj를 구한다. 만약 k가 k가 될 수 있는 최댓값을 초과하면 방향 전환이 불가능하다. 

4. visited [n-1, n-1, k]의 최솟값을 리턴한다.

구현

def solution(board):
    v1 = BFS(board, (0,0,'d',0, 0))
    v2 = BFS(board, (0,0,'r',0, 0))
    return min(v1+v2)

def BFS(board, start):
    l = len(board)
    mk = l*l
    visited = {}
    ns = [start]
    result = []
    while ns:
        dum = []
        for n in ns:
            if n[0] == l -1 and n[1] == l -1:
                result.append(n[3])
            for ad in adjs(board, n, visited, mk):
                dum.append(ad)
        ns = dum
    return result

def adjs(board, n, visited, mk):
    result = []
    x, y, o, c, k = n[0], n[1], n[2], n[3], n[4]
    dirs = [(1,0,'d'), (-1,0,'u'), (0,1,'r'), (0, -1,'l')]
    for d in dirs:
        nx, ny, no = x + d[0], y + d[1], d[2]
        nc = c + 600
        if  0 <= nx < len(board) and 0 <= ny < len(board) and board[nx][ny] == 0:
            if no == o:
                nc = c + 100
                if (nx, ny, k) not in visited:
                    visited[(nx, ny, k)] = nc
                    result.append((nx, ny, no, nc, k))
            else:
                if (nx, ny, k + 1) not in  visited and k < mk:
                    visited[(nx, ny, k+1)] = nc
                    result.append((nx, ny, no, nc, k+1))

    return result

좀더 좋은 코드 Dynamic programing이용

문제 4 :  visited와 회전을 고려하는 문제 - 블록 이동하기

https://programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

문제는 대략 이렇습니다
면적을 가지는 물체의 최단경로 탐색 문제입니다.

문제를 읽고 드는 생각
문제를 읽고

1. adj에 회전을 추가해야겠다.

2. 방문 처리 다시 정의해야겠다.

이 둘을 생각해야 합니다.

 

의사 코드 작성

1. 회전을 구현한다.

2. 방문처리를 visted = { (x1, y1, x2, y2 ) , (x2, y2, x1, y1)}형식으로 하는 BFS를 진행한다.

3. 마지막 원소에 대해서 최솟값을 정답을 제출한다.

 

!!!!!!!!!!!!!!!!!!시간 초과 판정을 받는 구현!!!!!!!!!!!!!!!!

def solution(board):
    BFS = _BFS
    n = len(board)
    board = [[1] + b + [1] for b in board]
    board = [[1] * (n + 2)] + board + [[1] * (n + 2)]
    return BFS(board)

def _BFS(board):
    #visited = {((x1, y1, x2, y2)) : count}
    adj = _adj
    ck = len(board)-2
    l = len(board)
    visited = set()
    start = (1,1,1,2)
    ns = [start]
    count = 0
    while ns != []
        dum = set()
        for n in ns:
            visited.add(n)
            visited.add((n[2], n[3], n[0], n[1]))
            if (n[2], n[3]) == (ck, ck):
                return count
            for ad in adj(board, n):
                if ad not in visited:
                    dum.append(ad)
        ns = dum
        count += 1
    return -1

def _adj(board, n):
    l = len(board)
    x1, y1, x2, y2 = n
    moves = [(1,0),(-1,0),(0,1),(0,-1)]
    result = []
    for move in moves:
        nx1, ny1 = x1 + move[0], y1 + move[1]
        nx2, ny2 = x2 + move[0], y2 + move[1]
        if board[nx1][ny1] == 0 and board[nx2][ny2] == 0:
            result.append( (nx1, ny1, nx2, ny2) )
    x1m, x2m = x1 - 1, x2 - 1
    y1m, y2m = y1 - 1, y2 - 1
    x1p, x2p = x1 + 1, x2 + 1
    y1p, y2p = y1 + 1, y2 + 1
    if x1 == x2:
        #시계
        if board[x2m][y2] == 0 and board[x2m][y2m] == 0:
            result.append( (x2m, y2m, x1, y1) )
        if board[x1p][y1] == 0 and board[x1p][y1p] == 0:
            result.append( (x2, y2, x1p, y1p) )
        #반식계
        if board[x2p][y2] == 0 and board[x2p][y2m] == 0:
            result.append( (x1, y1, x2p, y2m) )
        if board[x1m][y1] == 0 and board[x1m][y1p] == 0:
            result.append( (x1m,y1p, x2, y2) )
    else:
        #시계
        if board[x2][y2p] == 0 and board[x2m][y2p] == 0:
            result.append( (x1,y1, x2m, y2p) )
        if board[x1][y1m] == 0 and board[x1p][y1m] == 0:
            result.append( (x1p, y1m, x2, y2) )
        #반시계
        if board[x2][y2m] == 0 and board[x2m][y2m] == 0:
            result.append( (x2m, y2m, x1, y1) )
        if board[x1][y1p] == 0 and board[x1p][y1p] == 0:
            result.append( (x2, y2, x1p,y1p) )
                
    return result

위 구현에는 문제가 있습니다.

정답을 제출해 보면 시간 초과 판정을 받습니다.

왜 그럴까요?

실제 저도 이 것 때문에 2-3일 동안 고생을 했습니다.

처음 구현하시는 분들은 틀리는 것은 당연한 것이니 좌절하지 맙시다.

    while ns != []  <<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 여기가 문제 2
        dum = set()
        for n in ns:
            visited.add(n)
            visited.add((n[2], n[3], n[0], n[1]))
            if (n[2], n[3]) == (ck, ck):
                return count
            for ad in adj(board, n): <<<<<<<<<<<<<<<<<<<< 여기가 문제 1 
                if ad not in visited:
                    dum.append(ad)
        ns = dum
        count += 1
    return -1

틀린 부분은 위 코드에서 ad를 dum에 추가할지 안 할지에서 문제가 있었습니다.

ns loop안에 존재하기 때문에 dum에 ns의 성분이 포함되어 있습니다.

예를 들어 ns = [ n1, n2 , n3 ]라고 가정해 보고 코드를 따라가 봅시다.

n1에 대해 vsited에 추가하고 adj의 성분이 visited에 존재하는지 체크 한 다음 dum에 보관합니다.

이때 n2, n3와 같은 성분이 추가될수 있습니다.

그렇기에 이러한 문제가 없도록 처리를 해주어야 합니다.

저의 경우 loop를 나누어 사용하는 방법을 선택하였습니다. 

 

두번째는 ns를 리스트 자료구조로 이용한 것입니다.

우리가 사용하는 논리에선 성분들이 순차적으로 메모리에 저장할 필요가 없습니다.

그렇기에 훨씬 빠른 set() 자료구조를 사용하면 좋습니다.

 

정답 판정 구현

이제부터는 ns를 구현 시 set을 이용합시다.

또한 다음 ns를 구성할때 사용된 성분이 다시 사용될 수 있습니다.

그래서 visted를 처리하는 부분과 adj를 처리하는 부분을 독립적으로 for loop를 사용합시다.

def solution(board):
    BFS = _BFS
    n = len(board)
    board = [[1] + b + [1] for b in board]
    board = [[1] * (n + 2)] + board + [[1] * (n + 2)]
    return BFS(board)

def _BFS(board):
    #visited = {((x1, y1, x2, y2)) : count}
    adj = _adj
    ck = len(board)-2
    l = len(board)
    visited = set()
    start = (1,1,1,2)
    ns = {start}
    count = 0
    while ns != {}:
        dum = set()
        for n in ns:
            visited.add(n)
            if (n[2], n[3]) == (ck, ck):
                return count
        
        for n in ns:
            for ad in adj(board, n):    
                if ad not in visited:
                    dum.add(ad)
        ns = dum
        count += 1
    return -1

def _adj(board, n):
    l = len(board)
    x1, y1, x2, y2 = n
    moves = [(1,0),(-1,0),(0,1),(0,-1)]
    result = []
    for move in moves:
        nx1, ny1 = x1 + move[0], y1 + move[1]
        nx2, ny2 = x2 + move[0], y2 + move[1]
        if board[nx1][ny1] == 0 and board[nx2][ny2] == 0:
            result.append( (nx1, ny1, nx2, ny2) )
    x1m, x2m = x1 - 1, x2 - 1
    y1m, y2m = y1 - 1, y2 - 1
    x1p, x2p = x1 + 1, x2 + 1
    y1p, y2p = y1 + 1, y2 + 1
    if x1 == x2:
        #시계
        if board[x2m][y2] == 0 and board[x2m][y2m] == 0:
            result.append( (x2m, y2m, x1, y1) )
        if board[x1p][y1] == 0 and board[x1p][y1p] == 0:
            result.append( (x2, y2, x1p, y1p) )
        #반식계
        if board[x2p][y2] == 0 and board[x2p][y2m] == 0:
            result.append( (x1, y1, x2p, y2m) )
        if board[x1m][y1] == 0 and board[x1m][y1p] == 0:
            result.append( (x1m,y1p, x2, y2) )
    else:
        #시계
        if board[x2][y2p] == 0 and board[x2m][y2p] == 0:
            result.append( (x1,y1, x2m, y2p) )
        if board[x1][y1m] == 0 and board[x1p][y1m] == 0:
            result.append( (x1p, y1m, x2, y2) )
        #반시계
        if board[x2][y2m] == 0 and board[x2m][y2m] == 0:
            result.append( (x2m, y2m, x1, y1) )
        if board[x1][y1p] == 0 and board[x1p][y1p] == 0:
            result.append( (x2, y2, x1p,y1p) )
                
    return result

 

백준에서 풀어보면 좋은 문제들

아래의 문제들은 백준에서 제공하는 문제입니다.

만약 위의 내용을 명확하게 이해했는지 판단을 원한다면 아래의 두 문제를 풀어봅시다.

 

회전

https://www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

visited 변형

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

visited 변형

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이