[python code review] 17주차 (미로1, Contact, 간단한 압축 풀기)

[미로1]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD 

SW Expert Academy

이 문제의 경우 dfs와 bfs 두가지 방식으로 모두 구현할 수 있다.

출발지에 도달하는 경우 dfs는 return문을 걸어 재귀를 빠져나가고 bfs는 while문을 break해주는 방식으로 풀이하였다.

(nx, ny)가 방문하지 않는 좌표라면 이동할 수 있는 경우이기 때문에 탐색을 이어가고 visited[nx][ny] = 1로 방문 처리한다.

 

[dfs : 정답 코드]

def dfs(x, y):
    global result
    moves = [(1,0),(0,1),(-1,0),(0,-1)]
 
    if maps[x][y] == 3:
        result = 1
        return
 
    for dx, dy in moves:
        nx = dx + x
        ny = dy + y
        if not (0 <= nx < 16 and 0 <= ny < 16):
            continue
        if result: return
        if not visited[nx][ny] and maps[nx][ny] != 1:
            visited[nx][ny] = 1
            dfs(nx, ny)
 
 
for _ in range(10):
    result = 0
    tc = int(input())
    visited = [[0]*16 for _ in range(16)]
    maps = [list(map(int, list(input()))) for _ in range(16)]
    dfs(1, 1)
    print(f'#{tc}', result)

 

[bfs : 정답 코드]

from collections import deque


def bfs(x, y):
    global answer
    deq = deque([[x, y]])
    moves = [[1,0],[0,1],[0,-1],[-1,0]]
    visited = [[0]*16 for _ in range(16)]
    visited[x][y] = 1

    while deq:
        x, y = deq.popleft()
        
        if board[x][y] == 3:
            answer = 1
            break
        for dx, dy in moves:
            nx = dx + x; ny = dy + y
            if 0 <= nx < 16 and 0 <= ny < 16:
                if board[nx][ny] != 1 and not visited[nx][ny]:
                    visited[nx][ny] = 1
                    deq.append([nx, ny])

                    
for _ in range(10):
    tc = int(input())
    answer = 0
    board = [list(map(int, list(input()))) for _ in range(16)]
    bfs(1, 1)
    print(f'#{tc}', answer)

 

[Contact]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD&categoryId=AV15B1cKAKwCFAYD&categoryType=CODE&problemTitle=contact&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

[정답 코드]

딕셔너리 dic에 레벨 별 노드 정보들을 list 형태로 저장했다. 

bfs로 탐색 후 가장 마지막 level 정보를 담고 있는 변수 level을 key로 dic에 접근하면

해당 level에 존재하는 노드들을 알 수 있고 max 함수를 통해 최대 노드 번호를 구한다. 

from collections import deque, defaultdict

def bfs(start):
    deq = deque([(start, 0)])
    visited = [False for _ in range(101)]
    visited[start] = True
    dic = defaultdict(list) # key:value = level:[노드1, 노드2...]
    level = 0
    
    while deq:
        node, level = deq.popleft()
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                deq.append((next_node, level+1))
                dic[level+1].append(next_node)

    return max(dic[level])


for tc in range(1, 11):
    n, m = map(int, input().split())
    lst = list(map(int, input().split()))
    graph = [set() for _ in range(101)]
    for i in range(0, n, 2):
        a, b = lst[i], lst[i+1]
        graph[a].add(b)
    answer = bfs(m)
    print(f'#{tc}', answer)

 

[간단한 압축 풀기]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PmkDKAOMDFAUq

SW Expert Academy

[정답 코드]

기본적인 문자열 슬라이싱 문제이다.

빈 문자열 answer에 가능한 문자열을 전부 담고 10개씩 slicing하여 출력하면 된다.

for tc in range(1, int(input())+1):
    answer = ''
    print(f'#{tc}')
    for _ in range(int(input())):
        alpha, n = input().split()
        n = int(n)
        answer += alpha*n
    for i in range(0, len(answer), 10):
        print(answer[i:i+10])