티스토리 뷰

알고리즘/BOJ

[BOJ-2206] 벽부수고 이동하기

개발하는 후딘 2020. 3. 1. 22:14
728x90
반응형

https://www.acmicpc.net/problem/2206

 

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동

www.acmicpc.net

[ 코드]

# -*- coding: utf-8 -*-
import sys
from collections import deque
N,M =0,0
MAP=None
visited=None
result=1001 #초기화
q=deque()

#현위치의 상/하/좌/우
dy=[-1,1, 0,0]
dx=[0,0,-1, 1]

def isRange(y,x):
    global N,M
    if (y>=0 and y<N) and (x>=0 and x<M):
        return True
    return False

def bfs():
    global MAP, visited, N, M, result
    while q:
        y,x, d, break_cnt= q.popleft()

        #도착지점 도달하면 종료
        if (y==N-1) and (x==M-1):
            result=d
            break
        
        #현위치의 상/하/좌/우 방문
        for i in range(4):
            nexty=y+dy[i]
            nextx=x+dx[i]
            
            # N행M열 배열의 원소인가?
            if (isRange(nexty, nextx)) and (visited[nexty][nextx]>break_cnt):
                if MAP[nexty][nextx]=='0': #벽이 아닌경우
                    visited[nexty][nextx]=break_cnt
                    q.append((nexty, nextx, d+1, break_cnt))
                    
                else: #벽
                    if break_cnt==0: #벽을 뚫은 횟수가 0번이면
                        visited[nexty][nextx]=break_cnt+1
                        q.append((nexty, nextx, d+1, break_cnt+1))
        
        
def main():
    global N,M, MAP, visited, result
    #N: 세로, M: 가로
    N,M=map(int, sys.stdin.readline().split())
    MAP=[list(sys.stdin.readline().strip()) for _ in range(N)]
    visited=[[1001]*M for _ in range(N)]
    
    #큐에 시작점 먼저 추가(시작점y좌표, 시작점x좌표, 경로개수 1, 벽부수기 횟수 0회)
    q.append((0,0,1,0))
    bfs()
    if result==1001:
        print(-1)
    else:
        print(result)

if __name__=='__main__':
    main()

 

 

[참고]

https://www.acmicpc.net/board/view/27386

 

글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

[삽질 코드 1]

- 결과: 10%~20% 쯤에서 틀렸다고 뜹니다

- 반례

7 3

000

110

000

011

000

111

110

답: 13

출력: -1

# -*- coding: utf-8 -*-
import sys
from collections import deque
N,M =0,0
MAP=None
visited=None
q=deque()

#현위치의 상/하/좌/우
dy=[-1,1, 0,0]
dx=[0,0,-1, 1]

def isRange(y,x):
    global N,M
    if (y>=0 and y<N) and (x>=0 and x<M):
        return True
    return False

def bfs():
    global MAP, visited, N, M
    while q:
        y,x, d, break_cnt= q.popleft()
        print('y={0}, x={1}, cnt={2}, break_cnt={3}'.format(y,x, d, break_cnt))

        if (y==N-1 and x==M-1):
            return d

        else:
            #아직 방문안한상태이고, break_cnt>=0이라면
            if (not visited[y][x]) and (break_cnt>=0):
                visited[y][x]=True #현위치 방문
                street_cnt=0 #도로개수 카운트
                
                #현위치의 상/하/좌/우 방문
                for i in range(4):
                    nexty=y+dy[i]
                    nextx=x+dx[i]
                    
                    # N행M열 배열의 원소인가?
                    if isRange(nexty, nextx):
                        if not visited[nexty][nextx]:
                            if MAP[nexty][nextx]=='0':
                                q.append((nexty, nextx, d+1, break_cnt))
                            elif (MAP[nexty][nextx]=='1') and (break_cnt==1):
                                q.append((nexty, nextx, d+1, break_cnt-1))
 
    #큐가 빌때까지 도달하지 못했다면
    return -1
        
        
def main():
    global N,M, MAP, visited
    #N: 세로, M: 가로
    N,M=map(int, sys.stdin.readline().split())
    MAP=[list(sys.stdin.readline().strip()) for _ in range(N)]
    visited=[[False]*M for _ in range(N)]
    
    #큐에 시작점 먼저 추가(시작점y좌표, 시작점x좌표, 경로개수 1, 벽부수기 횟수 1회)
    q.append((0,0,1,1))
    result=bfs()
    print(result)

if __name__=='__main__':
    main()

 

[삽질 코드 2]

- 결과: 35% 쯤에 틀렸다고 뜹니다 ㅠㅠ

- 반례

6 4

0100

0110

1000

0000

0111

0000

답:9

출력: 15

# -*- coding: utf-8 -*-
import sys
from collections import deque
N,M =0,0
MAP=None
visited=None
q=deque()

#현위치의 상/하/좌/우
dy=[-1,1, 0,0]
dx=[0,0,-1, 1]

def isRange(y,x):
    global N,M
    if (y>=0 and y<N) and (x>=0 and x<M):
        return True
    return False

def bfs():
    global MAP, visited, N, M
    while q:
        y,x, d, break_cnt= q.popleft()

        if (y==0 and x==0):
            return d
        else:
            #아직 방문안한상태이고, break_cnt<2이라면
            if (not visited[y][x]) and (break_cnt<2):
                visited[y][x]=True #현위치 방문
                street_cnt=0 #도로개수 카운트
                
                #현위치의 상/하/좌/우 방문
                for i in range(4):
                    nexty=y+dy[i]
                    nextx=x+dx[i]
                    
                    # N행M열 배열의 원소인가?
                    if isRange(nexty, nextx):
                        if (not visited[nexty][nextx]) and (MAP[nexty][nextx]=='0'):
                            q.append((nexty, nextx, d+1, break_cnt))
                            street_cnt+=1
                                
                #현위치의 상/하/좌/우에 도로가 없다면..
                if street_cnt<1:
                    # 벽을 뚫는다.
                    for i in range(4):
                        nexty=y+dy[i]
                        nextx=x+dx[i]
                        if isRange(nexty, nextx):
                            if (not visited[nexty][nextx]) and (MAP[nexty][nextx]=='1'):
                                q.append((nexty, nextx, d+1, break_cnt+1))
                        

    #큐가 빌때까지 도달하지 못했다면
    return -1
        
        
def main():
    global N,M, MAP, visited
    #N: 세로, M: 가로
    N,M=map(int, sys.stdin.readline().split())
    MAP=[list(sys.stdin.readline().strip()) for _ in range(N)]
    visited=[[False]*M for _ in range(N)]
    
    #큐에 시작점 먼저 추가(시작점y좌표, 시작점x좌표, 경로개수 1, 벽부수기 횟수 0회)
    q.append((N-1,M-1,1,0))
    result=bfs()
    print(result)

if __name__=='__main__':
    main()

[ 코드 3]

-참고 코드: https://kim6394.tistory.com/search/2206

# -*- coding: utf-8 -*-
import sys
from collections import deque
N,M =0,0
MAP=None
visited=None
result=1001 #초기화
q=deque()

#현위치의 상/하/좌/우
dy=[-1,1, 0,0]
dx=[0,0,-1, 1]

def isRange(y,x):
    global N,M
    if (y>=0 and y<N) and (x>=0 and x<M):
        return True
    return False

def bfs():
    global MAP, visited, N, M, result
    while q:
        y,x, d, break_cnt= q.popleft()

        #도착지점 도달하면 종료
        if (y==N-1) and (x==M-1):
            result=d
            break
        
        #현위치의 상/하/좌/우 방문
        for i in range(4):
            nexty=y+dy[i]
            nextx=x+dx[i]
            
            # N행M열 배열의 원소인가?
            if (isRange(nexty, nextx)) and (visited[nexty][nextx]>break_cnt):
                if MAP[nexty][nextx]=='0': #벽이 아닌경우
                    visited[nexty][nextx]=break_cnt
                    q.append((nexty, nextx, d+1, break_cnt))
                    
                else: #벽
                    if break_cnt==0: #벽을 뚫은 횟수가 0번이면
                        visited[nexty][nextx]=break_cnt+1
                        q.append((nexty, nextx, d+1, break_cnt+1))
        
        
def main():
    global N,M, MAP, visited, result
    #N: 세로, M: 가로
    N,M=map(int, sys.stdin.readline().split())
    MAP=[list(sys.stdin.readline().strip()) for _ in range(N)]
    visited=[[1001]*M for _ in range(N)]
    
    #큐에 시작점 먼저 추가(시작점y좌표, 시작점x좌표, 경로개수 1, 벽부수기 횟수 0회)
    q.append((0,0,1,0))
    bfs()
    if result==1001:
        print(-1)
    else:
        print(result)

if __name__=='__main__':
    main()

 

728x90
반응형
저작자표시

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ-2606] 바이러스  (0) 2020.03.02
[BOJ-11066] 파일합치기  (0) 2020.03.02
[BOJ-2178] 미로탐색  (0) 2020.03.01
[BOJ-1520]내리막길  (0) 2020.03.01
[BOJ-11057] 오르막수  (0) 2020.02.29
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2024/05   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함