[백준] 6191 : Cows on Skates (Python)

 

출처 : https://www.acmicpc.net/problem/6191

 

 

---

 

아이디어

장애물로 구분되는 2차원 행렬이라는 점과 인접한 상하좌우 칸으로 점점 확장해나가는 요구사항을 지니고 있으므로, 그래프 탐색 유형의 문제임을 알 수 있다.

 

DFS vs BFS

'적어도 1가지 방법이 존재하고, 해당 경로를 출력해라.'

해당 요구사항을 통해, 경로는 1가지만 존재하며 지나온 좌표들을 모두 출력하라는 인사이트를 알 수 있다. 최소/최대의 경로길이가 아닌, 1가지의 경로 출력이므로 DFS/BFS를 모두 사용 가능하다. 필자는 BFS를 선택하였다.

 

Queue 원소 형식

다음의 시각화 그래프를 통해 알아보자.

상하로 이동가능한 자식 노드 2개의 서브트리를 포함하는 루트 트리

(1,2)로 갈때는 부모의 경로 배열에 더해지고, 마찬가지로 (1,3)으로 갈때도 부모 배열에서 더해진다. 즉, 상하좌우 각 케이스에 따른 경로를 부모 배열을 유전으로 받아 추가 및 저장해나가는 것이 핵심이므로, 다음과 같이 ADT를 설계할 수 있다.

• ADT(Queue) : [(노드의 r좌표, 노드의 c좌표, 해당노드 경로 배열 [])] 
• 정리 : [ (r, c, [] ) ]

 

방문처리 배열 Visited 설정 : Global vs Local

전역으로 가정하고 위의 시각화 사진과 함께 경로 저장의 과정을 자세히 알아보자. (1,2)의 자식노드인 (1,4), (1,5)에다가 (1,3)을 추가했다고 생각해보자.

[ (1,1), (1,2) ] 차례에서 (1,3)은 이미 방문처리가 되었기에, 큐에 삽입되지 않는다. 그러나, 다음의 상황을 비교해보면, (1,3)은 삽입을 하지 않아도 된다.

• [(1,1), (1,2), (1,3)]은 큐에 존재하던 [(1,1), (1,3)]과 유사한 경로이다.
• 즉, [(1,1), (1,2), (1,3)]은 (1,1)에서 (1,3)까지 돌아가는 경로이다. (길을 헤매다 이제 도착했어 == 길을 돌아왔어)

정리하자면, 부모 노드의 레벨에 존재하는 친척(부모의 형제 노드) 노드는 삽입하지 않아도 된다는 의미이다. 그러므로, 방문처리는 전역으로 설정하는 것이 좋음을 알 수 있다.

 

이를 통해 프로그램을 구현하면 문제를 쉽게 해결할 수 있다.

 

정답 코드

# https://www.acmicpc.net/problem/6191
# Cows on Skates
# 그래프 탐색, BFS, DFS

input=__import__('sys').stdin.readline
deque=__import__('collections').deque

def bfs(sx,sy):
    q=deque([(sx,sy,[(sx,sy)])]) # x,y,path
    visited[sx][sy]=1
    
    while q:
        x,y,path=q.popleft()
        for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]: #하우상좌
            nx=x+dx
            ny=y+dy
            if 0<=nx<r and 0<=ny<c:
                if (nx,ny)==(r-1,c-1):
                    path.append((nx,ny))
                    return path
                if board[nx][ny]!='*' and not visited[nx][ny]:
                    visited[nx][ny]=1
                    tmp=[i for i in path]+[(nx,ny)]
                    q.append((nx,ny,tmp))


r,c=map(int,input().split())
board=[[*input()][:-1] for _ in range(r)]
visited=[[0]*c for _ in range(r)]

history=bfs(0,0)
for i,j in history:
    print(i+1,j+1)