광규니
광규니네
광규니
전체 방문자
오늘
어제
  • 분류 전체보기 (154)
    • 알고리즘 (100)
      • 알고리즘 개념 (2)
      • 문제 풀이 (96)
    • 주절주절 (19)
      • 자격증, 활동 후기 (4)
      • 전시회 후기 (3)
      • 이모저모 (2)
      • 회고 (3)
      • 뜨럼 (7)
    • 운영체제 (9)
    • 개발 지식 (9)
      • Apple Watch (4)
      • MySQL (2)
      • Eclipse (1)
      • XCode (1)
    • 네트워크 공부 (1)
    • 데이터베이스 공부 (5)
    • Java 공부 (7)
    • TMP (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 애플워치 앱 만들기
  • OS
  • 애플워치 앱
  • 합주
  • 백준
  • 자바
  • DP
  • BOJ
  • 알고리즘
  • 오블완
  • 운영체제
  • 프로그래머스
  • 티스토리챌린지
  • 드린이
  • 컴퓨터 사이언스
  • 개념
  • 파이썬
  • 다이나믹 프로그래밍
  • BFS
  • 구현

최근 댓글

최근 글

티스토리

250x250
hELLO · Designed By 정상우.
광규니

광규니네

알고리즘/문제 풀이

[Python/파이썬 백준 2206] 벽 부수고 이동하기(BFS)

2021. 3. 2. 16:38
반응형

www.acmicpc.net/problem/2206

 

 

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로

www.acmicpc.net

풀이


처음 문제를 봤을 때 이중포문 돌려서 min 값 비교해가면서 풀어봤는데
시간초과가 났습니당!
고래서 검색 결과 check 리스트를 삼중 리스트를 사용해서 
z값을 비교해가면서 부술경우 안부술경우를 나누어 풀이

# 이중포문 돌려서 각각 0으로 바꿔서 min값 비교
# 해봤다가 시간초과 돼서 보니까 3차원 쓰라고한당
from collections import deque
import sys
graph=[]
dx=[1,-1,0,0]
dy=[0,0,-1,1]
minsize=sys.maxsize

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

for i in range(n):
  graph.append(list(map(int,input())))

check=[[[-1]*2 for _ in range(m)] for _ in range(n)]

def bfs():
  queue=deque()
  queue.append((0,0,0))
  check[0][0][0]=1
  
  while queue:
    x,y,z = queue.popleft()
    for i in range(4):
      nx= x + dx[i]
      ny= y + dy[i]
      if 0<=nx<n and 0<=ny<m :
        #벽을 부술경우와 안부술경우 두가지로 나눈다
        # check 3차원 리스트로 z가 부순경우 안부수경우 판단
        
        # 안부술경우, 한번 부수고 나선 z=1에다가 담는다
        if graph[nx][ny]==0 and check[nx][ny][z]==-1:
          check[nx][ny][z]=check[x][y][z]+1
          queue.append((nx,ny,z))
        # 벽을 만나서 처음으로 부수는 경우 
        elif z==0 and graph[nx][ny]==1 and check[nx][ny][z+1]==-1:
          check[nx][ny][z+1]=check[x][y][z]+1
          queue.append((nx,ny,z+1))

bfs()

ret1,ret2 =check[n-1][m-1][0],check[n-1][m-1][1]

if ret1==-1 and ret2!=-1:
  print(ret2)
elif ret1!=-1 and ret2==-1:
  print(ret1)
else:
  print(min(ret1,ret2))

반응형

'알고리즘 > 문제 풀이' 카테고리의 다른 글

[Python/파이썬 백준 13460] 구슬탈출2 (BFS)  (0) 2021.03.09
[Python/파이썬 백준 2468] 안전 영역(BFS)  (0) 2021.03.04
[Python/파이썬 백준 5104] 스타트링크(BFS)  (0) 2021.03.04
[Python/파이썬 백준 1012] 유기농 배추(BFS)  (0) 2021.02.25
[Python/파이썬, Java/자바 백준 7576] 토마토(BFS)  (0) 2021.02.24
    '알고리즘/문제 풀이' 카테고리의 다른 글
    • [Python/파이썬 백준 2468] 안전 영역(BFS)
    • [Python/파이썬 백준 5104] 스타트링크(BFS)
    • [Python/파이썬 백준 1012] 유기농 배추(BFS)
    • [Python/파이썬, Java/자바 백준 7576] 토마토(BFS)
    광규니
    광규니
    공부 및 일상 올리기~

    티스토리툴바