[알고리즘] 백준 2178 (파이썬)

이 문제는 bfs 관련 문제이다.
하지만 처음 접근 할 때 dfs문제로 인식하고 풀었다..
결국 오른쪽 아래 방향으로 이동하기 때문에 오른쪽을 우선으로 접근하는 것과 아래를 우선으로 접근하는 방법 2가지를 따로 만들어 둘 중 낮은 count값을 출력하도록 했다.
예제는 모두 통과했지만 답이 틀렸었고, 다시 생각해보니 오른쪽이든 아래든 막혀서 다시 돌아오는 경우가 생겼다. 따라서 새로운 map을 만들어 탐색할 때마다 1을 증가시키는 값을 저장하도록 했다. 그런데 stack으로 계산하니 한 번 잘못 길을 들면(오래 걸리는 경로) 그대로 계속 가기 때문에 값이 크게 나온다. 따라서 queue를 통해 순간 순간 가장 최소인 값을 가지게 했다. 처음 dfs로 접근할 때에는 종점에 도착하면 바로 break를 걸어주었는데 bfs식 queue로 접근하면 그렇게 안해주어도 된다.

+추가로 배운점

1. 리스트를 복사할 때에 그냥 a=b이런 식으로 접근했는데, 이러면 id(c++로 생각하면 pointer) 즉 주소 값이 똑같게 된다. 따라서 list a를 바꾸면 b가 동시에 바뀐다. 이를 방지하기 위해선 다양한 방법이 있는데, 앞으로 문제를 풀 때에는 a=list(b) 또는 a=b.copy() 이 두가지만 사용해야 겠다.(가독성을 위해)

2. 또한 리스트를 copy를 통해 복사 했는데 계속 두 Map 리스트가 같이 바뀌는 점을 보고 계속 헤맸는데 list 안에 list가 있으면 copy를 할 때 제일 바깥 list만 다른 주소로 가져오고 안쪽 list는 주소가 그대로 유지된다. 따라서 for 문을 이용하여 각각 copy시켜주었다.

x,y=map(int,input().split())
mapmap=[list(map(int,input())) for i in range(x)]
map_1=[]
map_2=[]
for i in mapmap:
    map_1.append(i.copy())
    map_2.append(i.copy())
answer=[]
s = [[0]*y for i in range(x)]
s[0][0]=1
def fright(x,y):
    count=0
    dx=[0,-1,1,0]
    dy=[-1,0,0,1]
    stack=[[x,y]]
    map_1[x][y]=0
    while stack:
        next=stack.pop(0)
        # print(next[0],next[1])
        count+=1
        # if next[0]==len(map_1)-1 and next[1]==len(map_1[0])-1:
        #     break
        for i in range(4):
            nx=dx[i]+next[0]
            ny=dy[i]+next[1]
            if nx<0 or ny<0 or nx>=len(map_1)or ny>=len(map_1[0]):
                continue
            if map_1[nx][ny] == 1:
                stack.append([nx, ny])
                map_1[nx][ny] = 0
                s[nx][ny] = s[next[0]][next[1]] + 1

    answer.append(count)

# def fdown(map,x,y):
#     count=0
#     dx=[0,-1,0,1]
#     dy=[-1,0,1,0]
#     stack=[[x,y]]
#     map[x][y]=0
#     while stack:
#         next=stack.pop()
#         # print(next[0], next[1])
#         count+=1
#         if next[0]==len(map)-1 and next[1]==len(map[0])-1:
#             break
#         for i in range(4):
#             nx=dx[i]+next[0]
#             ny=dy[i]+next[1]
#             if nx<0 or ny<0 or nx>=len(map)or ny>=len(map[0]):
#                 continue
#             if map[nx][ny]==1:
#                 stack.append([nx,ny])
#                 map[nx][ny]=0
#     answer.append(count)

fright(0,0)
# fdown(mapmap,0,0)
# print(min(answer))
# print(s)
print(s[len(map_1)-1][len(map_1[0])-1])