[실버 I] 14940번. 쉬운 최단거리

 문제 

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

14940번: 쉬운 최단거리

 사용 언어 

Python3

 풀이 과정 

그래프 탐색 문제였고 문제를 읽어보니 이제 DFS보단 BFS를 사용해야할 것 같은 느낌이 들었다. 물론 DFS로도 풀 수는 있겠지만 풀고 나서 보니 대부분의 사람들이 정말 BFS로 풀었더라!

 

문제는 되게 짧았는데 코드로 구현하는 방법에 대한 고민과 몇 가지 조건을 처리해주는 방식이 고민됐다.

일단 나는 정답을 기록할 answer 리스트를 하나 따로 만들어서 기본값은 -1(도달할 수 없는 위치)로 초기화했다. 그리고 땅이 0인 경우에는 답도 무조건 0이기 때문에 0으로 변경해줬다.

BFS 로직을 짜는게 조금 헷갈렸는데, 델타값을 사용해서 상하좌우를 확인하는 것까진 항상 똑같지만 처음 도착한 땅에서 수행할 작업을 정의하는 게 가장 어려운 포인트인 것 같다.

 

어쨌든 맞았습니다!!가 뜨긴 했지만 그리고 다른 스터디원들에 비해 시간이 오래 걸려서 시간복잡도를 개선하기 위해 이것 저것 시도해봤다.

이후에 코드 개선을 해나가며 시간을 조금씩 줄인 과정을 아래에 적어보겠다.

 

 제출 답안 

from collections import deque
from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
graph = [input().split() for _ in range(n)]
answer = [[-1 for _ in range(m)] for _ in range(n)]
visit = [[False for _ in range(m)] for _ in range(n)]

for i in range(n):
    for j in range(m):
        if graph[i][j] == "0":
            answer[i][j] = 0
        # 목표 지점
        elif graph[i][j] == "2":
            tr, tc = i, j

q = deque([[tr, tc, 0]])
answer[tr][tc] = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

while q:
    current = q.popleft()
    cr, cc, cnt = current
    if not visit[cr][cc]:
        visit[cr][cc] = True
        for d in range(4):
            nr = cr + dx[d]
            nc = cc + dy[d]
            if 0 <= nr < n and 0 <= nc < m and not visit[nr][nc]:
                if graph[nr][nc] == "1":
                    answer[nr][nc] = cnt + 1
                    q.append([nr, nc, cnt + 1])

for i in range(n):
    print(*answer[i])

 

 코드 개선 

1. 먼저 숫자와 숫자를 비교하는 게 문자와 숫자를 비교하는 것보다 더 시간이 적게 걸릴수도 있지 않을까? 하는 생각으로 map을 사용해서 graph를 숫자로 바꿔줘봤다.

graph = [list(map(int, input().split())) for _ in range(n)]
...
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            answer[i][j] = 0
        # 목표 지점
        elif graph[i][j] == 2:
            tr, tc = i, j

➡ 오히려 시간이 늘어났다. 함수 실행 횟수가 중요하지 문자냐 숫자냐는 중요하지 않은 것 같다.

 

2. 그리고 역시 함수를 사용하지 않은 문제인 것 같아 BFS 함수로 묶어줘서 일부를 지역화시켜주었다.

from collections import deque
from sys import stdin
input = stdin.readline

def BFS(tr, tc, visit):
    q = deque([[tr, tc, 0]])
    answer[tr][tc] = 0
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]

    while q:
        current = q.popleft()
        cr, cc, cnt = current
        if not visit[cr][cc]:
            visit[cr][cc] = True
            for d in range(4):
                nr = cr + dx[d]
                nc = cc + dy[d]
                if 0 <= nr < n and 0 <= nc < m and not visit[nr][nc]:
                    if graph[nr][nc] == "1":
                        answer[nr][nc] = cnt + 1
                        q.append([nr, nc, cnt + 1])

if __name__ == "__main__":
    n, m = map(int, input().split())
    graph = [input().split() for _ in range(n)]
    answer = [[-1 for _ in range(m)] for _ in range(n)]
    visit = [[False for _ in range(m)] for _ in range(n)]

    for i in range(n):
        for j in range(m):
            if graph[i][j] == "0":
                answer[i][j] = 0
            # 목표 지점
            elif graph[i][j] == "2":
                tr, tc = i, j

    BFS(tr, tc, visit)

    for i in range(n):
        print(*answer[i])

➡ 줄어들 것 같았지만 이 정도의 차이를 예상하진 못했는데 아무래도 땅이 넓어서 while문을 계속 돌려야 하기 때문에 차이가 꽤 나는 것 같다.

 

3. 마지막으로 입력할 때 0인 경우와 2인 경우를 체크해서 for문을 한 번이라도 덜 돌게 해주었다.

from collections import deque
from sys import stdin
input = stdin.readline

def BFS(tr, tc, visit):
    q = deque([[tr, tc, 0]])
    answer[tr][tc] = 0
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]

    while q:
        current = q.popleft()
        cr, cc, cnt = current
        if not visit[cr][cc]:
            visit[cr][cc] = True
            for d in range(4):
                nr = cr + dx[d]
                nc = cc + dy[d]
                if 0 <= nr < n and 0 <= nc < m and not visit[nr][nc]:
                    if graph[nr][nc] == "1":
                        answer[nr][nc] = cnt + 1
                        q.append([nr, nc, cnt + 1])

if __name__ == "__main__":
    n, m = map(int, input().split())
    graph = []
    answer = [[-1 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        graph.append(input().split())
        for j in range(m):
            if graph[i][j] == "0":
                answer[i][j] = 0
            # 목표 지점
            elif graph[i][j] == "2":
                tr, tc = i, j

    visit = [[False for _ in range(m)] for _ in range(n)]
    BFS(tr, tc, visit)

    for i in range(n):
        print(*answer[i])

➡ 확실히 유의미한 차이를 보인다. 이런 실험(?) 결과를 앞으로 코드 구현시 잘 유념하며 짜야겠다.