13459 구슬탈출

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

13459번: 구슬 탈출

 

# BOJ_G1_13456_구슬 탈출 [2023-03-08] </br>
문제 : https://www.acmicpc.net/problem/13459

<접근법>
```
1. 우선 그래프이고, bfs사용 why? 경로가 여려개 존재 할 수 있으므로
#조건 체크
2. 상하좌우 4동작 파란구슬과 빨간 구슬이 동시에 움직인다는 것이 포인트!!!
3. 이때 한칸씩 움직이는 것이아니라 벽에 닿거나 구멍에 들어갈때까지 구르는게 포인트
4. 빨파 같은곳 안됨 파란색 구멍들어가는거 안됨
5. 10번이하로 빨간구슬 빼내는게 가능하냐?
6. 두구슬의 위치가 같다면, 많이 움직인 것을 무조건 한칸 빼줌
```
```python


from collections import deque
#조건 받기
n,m = map(int,input().split())
graph = [list(input().rstrip()) for _ in range(n)]
#print(graph)
#상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]



#bfs함수 만들기 : 주의점은 빨간색과 파란색 두개 동시에 해야한다는 것!!!!! 움직이는 것이 2개이다
def bfs(rx,ry,bx,by):
    q= deque()
    q.append((rx,ry,bx,by))
    #횟수 카운트
    cnt=0
    #방문 체크
    
    visited = []
    visited.append((rx,ry,bx,by))
    
    while q:
        for _ in range(len(q)):
            #큐에서 좌표 꺼내기
            rx,ry,bx,by = q.popleft()
            #만약 cnt >10 이면 0
            if cnt >10:
                print(0)
                return
            #만약 빨간공 구멍 들어가면 cnt 출력
            if graph[rx][ry]=='O':
                print(1)
                return
            #두개다 아니면 탐색 시작
            for i in range(4):
                #한번 기우리면 벽에 닿거나 구멍에 들어갈때까지
                nrx, nry = rx, ry
                while True:
                    #print(123)
                    nrx=nrx+dx[i]
                    nry=nry+dy[i]
                    #print(123)
                    if graph[nrx][nry]=='#':
                        #벽에 닿는다면?
                        nrx=nrx-dx[i]
                        nry=nry-dy[i]
                        break
                    if graph[nrx][nry]=='O':
                        break
                nbx, nby = bx, by
                while True:
                    nbx=nbx+dx[i]
                    nby=nby+dy[i]
                    if graph[nbx][nby] =='#':
                        nbx=nbx-dx[i]
                        nby=nby-dy[i]
                        break
                    if graph[nbx][nby] =='O':
                        break
                #파란구슬이 들어가면 안됨 continue로 무시
                if graph[nbx][nby]=='O':
                    continue
                #두구슬의 위치가 같다면 많이 움직인것이 뒤에것임!!!
                if nrx==nbx and nry==nby:
                    if abs(nrx-rx)+abs(nry-ry)>abs(nbx-bx)+abs(nby-by):
                        nrx=nrx-dx[i]
                        nry=nry-dy[i]
                    else:
                        nbx=nbx-dx[i]
                        nby=nby-dy[i]
                #방문한적이 없다 즉 움직였는데 새로운 위치 막다른 곳에 다달았다
                if (nrx,nry,nbx,nby) not in visited:
                    q.append((nrx,nry,nbx,nby))
                    visited.append((nrx,nry,nbx,nby))
        cnt+=1
    #만약 10회초과 했는데 구멍에 못들가면
    print(0)
                
                       


##빨간구슬과 파란구슬 좌표값 받기 => 그래야 처음 bfs 시작지점 정의가능
for i in range(n):
    for j in range(m):
        if graph[i][j]=='R':
            redx,redy = i,j
        
        elif graph[i][j]=='B':
            bluex,bluey = i,j

#bfs 시작
bfs(redx,redy,bluex,bluey)

#O를 0으로 착각했다 ㅜ
    
  
```

넘나 어려운것;; 구글링을 해서 풀었다..

 

 

해당 코드를 chat gpt에게 간결하고 깔끔하게 해달라고 물어봤다.

3번정도의 실패끝에 백준에 제출하면 통과하더라.. 

아마도 이번세대의 개발자는 chat gpt를 잘 활용하는 사람이 생산성이 확 올라가지 않을까?

물론 가독성이 떨어지는 부분도 있고 완벽하지는 않다.

 

from collections import deque

# 방문 여부 체크 함수
def is_visited(visited, red, blue):
    return (red, blue) in visited

# bfs 함수
def bfs(graph, red, blue):
    q = deque([(red, blue, 0)])
    visited = set([(red, blue)])
    
    while q:
        red, blue, cnt = q.popleft()
        if cnt > 10:
            return 0
        if graph[red[0]][red[1]] == 'O':
            return 1
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            new_red = red
            while graph[new_red[0]+dx][new_red[1]+dy] != '#' and graph[new_red[0]][new_red[1]] != 'O':
                new_red = (new_red[0]+dx, new_red[1]+dy)
            new_blue = blue
            while graph[new_blue[0]+dx][new_blue[1]+dy] != '#' and graph[new_blue[0]][new_blue[1]] != 'O':
                new_blue = (new_blue[0]+dx, new_blue[1]+dy)
            if graph[new_blue[0]][new_blue[1]] == 'O':
                continue
            if new_red == new_blue:
                if abs(new_red[0]-red[0])+abs(new_red[1]-red[1]) > abs(new_blue[0]-blue[0])+abs(new_blue[1]-blue[1]):
                    new_red = (new_red[0]-dx, new_red[1]-dy)
                else:
                    new_blue = (new_blue[0]-dx, new_blue[1]-dy)
            if not is_visited(visited, new_red, new_blue):
                q.append((new_red, new_blue, cnt+1))
                visited.add((new_red, new_blue))
                
    return 0


# 입력 받기
n, m = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(n)]

# 빨간 구슬, 파란 구슬 위치 찾기
red = blue = None
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'R':
            red = (i, j)
        elif graph[i][j] == 'B':
            blue = (i, j)

# bfs 실행
print(bfs(graph, red, blue))