8월 9일 수요일 코테

No. 1

 

 

-  문제 : BFS 탐색 / 네 방향 탈출 가능 여부 판별하기

https://www.codetree.ai/missions/2/problems/determine-escapableness-with-4-ways?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드 

시간초과남... ㅠ 쌤이하라는대로 했는데 왜 ... 

n,m = map(int,input().split())
result =0 

# 그래프 생성
graph = []
for _ in range(n):
    a= list(map(int,input().split()))
    graph.append(a)

# 그래프 좌표 찍기 
for i in range(n):
    for j in range(m):
        if graph[i][j] ==1:
            graph[i][j] = (i,j)
        
# 그래프 탐색 방향설정용 상 -> 시계방향
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]

# BFS 용 큐 
q =[(0,0)] 

# 그래프 탐색 
while q : # 큐에 값이 있는동안 계속 반복 
    k = q.pop(0) #값을 하나뺀다 (c,t)
    graph[k[0]][k[1]] = 'V'#해당점을 방문표시 
    


    for t in range(4):
        ddi = k[0]+di[t] #각 좌표값 위아래 검사하면서 큐에넣어야함.. 
        ddj = k[1]+dj[t]

        #범위 벗어나지 않게 조치 
        if  0 <= ddi < n and 0 <= ddj < m:
            exp = graph[ddi][ddj] 
        else: 
            continue

        if exp == (n-1,m-1):
            result = 1 #결과값을 1로 변경 
            break

        if exp != 0 and exp != 'V': #뱀이아니거나 방문하지 않았다면
            # 우하단에 도착했는지 확인하는코드 
            q.append(exp) #큐에 넣는다. 

#print(graph) #디버깅용
print(result)

코드 2 : queue 를 사용해봄  -> 소용없음 

from queue import Queue

n,m = map(int,input().split())
result =0 

# 그래프 생성
graph = []
for _ in range(n):
    a= list(map(int,input().split()))
    graph.append(a)

# 그래프 좌표 찍기 
for i in range(n):
    for j in range(m):
        if graph[i][j] ==1:
            graph[i][j] = (i,j)
        
# 그래프 탐색 방향설정용 상 -> 시계방향
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]

# BFS 용 큐 
q = Queue()
q.put((0,0))

# 그래프 탐색 

while q.qsize() != 0 : # 큐에 값이 있는동안 계속 반복 

    k = q.get() #값을 하나뺀다 (c,t)

    graph[k[0]][k[1]] = 'V'#해당점을 방문표시 
    


    for t in range(4):
        ddi = k[0]+di[t] #각 좌표값 위아래 검사하면서 큐에넣어야함.. 
        ddj = k[1]+dj[t]

        #범위 벗어나지 않게 조치 
        if  0 <= ddi < n and 0 <= ddj < m:
            exp = graph[ddi][ddj] 
            #print(exp) 디버깅용
        else: 
            continue

        if exp == (n-1,m-1):
            result = 1 #결과값을 1로 변경 
            break

        if exp != 0 and exp != 'V': #뱀이아니거나 방문하지 않았다면
            # 우하단에 도착했는지 확인하는코드 
            q.put(exp) #큐에 넣는다. 

#print(graph) #디버깅용
print(result)

 

 

 

새롭게 알게된것 

 

 

 

주의할점