[백준] 14940번: 쉬운 최단거리

문제

2차원 배열에 관한 BFS는 이제 전반적인 필수 로직은 파악이 가능하다.

⭐️가로 및 세로 방향의 dr, dc를 나누어 다음 칸에 대한 정보가 조건에 맞는지 확인하고 정보 업데이트⭐️

비슷한 문제_미로 탐색

이것만 알면 세부 조건문만 적당히 조절하면 쉽게 통과할 수 있다.
그런데 이번 문제는 특이하게 예상했던 것과 다르게 시간이 나와서 스터디 도중에 다들 당황했던 기억이 있어서 글을 써본다.

풀이 I

41372KB 728ms

mapN, mapM = map(int, input().split())
mapInfo = []
visited = [[0 for _ in range(mapM)] for _ in range(mapN)]
distance = [[-1 for _ in range(mapM)] for _ in range(mapN)]
startDot = ()

for i in range(mapN):
    eachRow = list(map(int, input().split()))
     # map을 만들어줄 때 2이면 시작 포인트를 잡는다.
    for j in range(len(eachRow)):
        if eachRow[j] == 2:
            startDot = (i, j)
    mapInfo.append(eachRow)

dr, dc = [1, 0, -1, 0], [0, 1, 0, -1]

# 일반적인 BFS 처리와 동일합니다.
def BFS(mapInfo, startDot):
    queue = [startDot]
    visited[startDot[0]][startDot[1]] = 1
    distance[startDot[0]][startDot[1]] = 0
    while queue:
        curN, curM = queue.pop(0)
        for i in range(4):
            newR, newC = curN+dr[i], curM+dc[i]
            # 방문하지 않은 곳이며 동시에 map 범위 안에 있는 곳만 검사합니다.
            if 0<=newR<mapN and 0<=newC<mapM and visited[newR][newC] == 0:
                if mapInfo[newR][newC] == 1:
                    distance[newR][newC] = distance[curN][curM] + 1
                    visited[newR][newC] = 1
                    queue.append([newR, newC])
                elif mapInfo[newR][newC] == 0: 
                    distance[newR][newC] = 0

BFS(mapInfo, startDot)

# map에서 0인 곳에 결과값이 -1이 나오는 경우 0으로 바꿔주는 처리
for i in range(mapN):
    for j in range(mapM):
        if distance[i][j] == -1 and mapInfo[i][j] == 0:
            distance[i][j] = 0
            
for eachRow in distance:
    print(*eachRow)

이런 식으로 처음에 구성을 했는데, 보다시피 출력 바로 위 반복문이 다소 거슬린다.
그런데 이게 없다면 다음과 같은 예제에서 답이 틀리게 나온다.

<반례>

입력
3 2
0 2
0 0
0 0

현재 결과
0 0
-1 0
-1 -1

// 왜냐하면 갈 수 없는 곳인 경우 아예 0으로 만들어줘야 하기 때문
예상 결과
0 0
0 0
0 0

그래서 한 번 방문처리한 결과로 -1이 나왔지만 애초에 0인 경우를 한 번 더 검사를 해서 해당 정보를 0으로 바꿔주는 처리를 추가적으로 한 것이다.
이 경우 2차원 배열을 총 세 번 도는 것이 되는데, 세 번까지 돌 필요가 있을까하는 의문을 가진 채 스터디를 진행한 결과 다음과 같은 해결책을 다시 도출할 수 있었다.

풀이 II

41376KB 756ms

mapN, mapM = map(int, input().split())
mapInfo = []
visited = [[0 for _ in range(mapM)] for _ in range(mapN)]
distance = [[-1 for _ in range(mapM)] for _ in range(mapN)]

startDot = ()

for i in range(mapN):
    eachRow = list(map(int, input().split()))
    # map을 만들어줄 때 2이면 시작 포인트를 잡고, 0이면 결과값에 0으로 설정한다.
    for j in range(len(eachRow)):
        if eachRow[j] == 2:
            startDot = (i, j)
        # 띠용? 시간 더 나오는 요인...!
        elif eachRow[j] == 0:
            distance[i][j] = 0
    mapInfo.append(eachRow)

dr, dc = [1, 0, -1, 0], [0, 1, 0, -1]

def BFS(mapInfo, startDot):
    queue = [startDot]
    visited[startDot[0]][startDot[1]] = 1
    distance[startDot[0]][startDot[1]] = 0
    while queue:
        curN, curM = queue.pop(0)
        for i in range(4):
            newR, newC = curN+dr[i], curM+dc[i]
            if 0<=newR<mapN and 0<=newC<mapM and visited[newR][newC] == 0:
                if mapInfo[newR][newC] == 1:
                    distance[newR][newC] = distance[curN][curM] + 1
                    visited[newR][newC] = 1
                    queue.append([newR, newC])
                elif mapInfo[newR][newC] == 0: 
                    distance[newR][newC] = 0

BFS(mapInfo, startDot)

for eachRow in distance:
    print(*eachRow)

위 풀이와의 차이는

for i in range(mapN):
    eachRow = list(map(int, input().split()))
    # map을 만들어줄 때 2이면 시작 포인트를 잡고, 0이면 결과값에 0으로 설정한다.
    for j in range(len(eachRow)):
        if eachRow[j] == 2:
            startDot = (i, j)
        # 띠용? 시간 더 나오는 요인...!
        elif eachRow[j] == 0:
            distance[i][j] = 0
    mapInfo.append(eachRow)

이 부분인데, 애초에 0인 부분을 만날 예정일 때 더 처리를 하지 않으니, BFS 돌기 전에 0으로 미리 처리를 한 것이다.
그래서 위에서 거슬렸던 반복문 하나를 제거할 수 있었는데,
시간이 대략 30ms 정도 더 나왔다...
근데 이유를 알 수 없다.

더 가관인 것은 다음 풀이에 한 번 더 볼 수 있다.

풀이 III

41372KB 788ms

(보완하려할수록 더 시간이 길어지는 매직)

mapN, mapM = map(int, input().split())
mapInfo = []
visited = [[0 for _ in range(mapM)] for _ in range(mapN)]
distance = [[-1 for _ in range(mapM)] for _ in range(mapN)]
startDot = ()

for i in range(mapN):
    eachRow = list(map(int, input().split()))
    # map을 만들어줄 때 2이면 시작 포인트를 잡고, 0이면 결과값에 0으로 설정합니다.
    for j in range(len(eachRow)):
        if eachRow[j] == 2:
            startDot = (i, j)
        # 띠용? 시간 더 나오는 요인...!
        elif eachRow[j] == 0:
            distance[i][j] = 0
    mapInfo.append(eachRow)

dr, dc = [1, 0, -1, 0], [0, 1, 0, -1]

# 일반적인 BFS 처리와 동일합니다.
def BFS(mapInfo, startDot):
    queue = [startDot]
    visited[startDot[0]][startDot[1]] = 1
    distance[startDot[0]][startDot[1]] = 0
    while queue:
        curN, curM = queue.pop(0)
        for i in range(4):
            newR, newC = curN+dr[i], curM+dc[i]
            # 방문하지 않은 곳이며 동시에 map 범위 안에 있는 곳만 검사합니다.
            if 0<=newR<mapN and 0<=newC<mapM and visited[newR][newC] == 0:
                if mapInfo[newR][newC] == 1:
                    distance[newR][newC] = distance[curN][curM] + 1
                    visited[newR][newC] = 1
                    queue.append([newR, newC])
                # 사실상 위에서 0 처리한 것때문에 없어도 되는 코드인데...
                # elif mapInfo[newR][newC] == 0: 
                   # distance[newR][newC] = 0

BFS(mapInfo, startDot)

for eachRow in distance:
    print(*eachRow)

풀이 II와 다른 점은 주석처리 한 부분이다.
미리 0으로 처리한 것이 중복된다고 생각하여 해당 부분을 삭제하고 돌렸더니, 시간이 II보다 30ms 더 나왔다...

아니 이게 도대체 어찌된 일!

시간 초과를 핸들링하기가 참 어렵고, 그래서 조금이라도 더 줄이려고 노력하는데,
이렇게 원인을 알기 어려우면 어떻게 결론을 지어야할 지 모르겠다.

우선은 A일 때는 B로 로직을 구현한다 라고 외우기 보다는
다양한 로직이 있다라고 생각하고
해당 로직에 대한시간은 각각 해보고 파악해야 겠다는 생각이 든다.

코딩테스트... 이럴 때면 머리가 지끈하다...