백준 / 23352번 방탈출 - bfs / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 방탈출

문제 사이트: https://www.acmicpc.net/problem/23352

 

 

---

나의 풀이

 

세세한 방문처리 잘 봐야하고 

임의의 방에서 출발한다는 것 -> 꼭 모서리 부분부터 출발하는것은 아님

나는 격자 테두리부분으로만 출발하는 줄 알았는데 아니드라

 

그리고 큐에 넣을 첫번째 노드 방문처리 확실하게 하기

 

길이가 같은 노드는 저장해뒀다가 나중에 문제 조건에서 의미하는것 잘 확인하고 출력

 

n,m 이거 위치도 제대로 봐야함 그대로 했다가 x,y 바뀌었음;;

import sys
from collections import deque
# 임의의 방에서 다른 방으로 이동할 때는 항상 두 방 사이의 최단 경로로 이동한다.
# 1번을 만족하는 경로 중 가장 긴 경로의 시작 방과 끝 방에 적힌 숫자의 합
# 만약 위 2가지 조건을 만족하는 경로가 여러 개라면,
# 시작 방과 끝 방에 적힌 숫자의 합이 가장 큰 값이 비밀번호가 된다.

# 시작 방과 끝 방은 동일한 위치일 수도 있다.
input = sys.stdin.readline
n, m = map(int,input().split()) # m 행 n 열
maps = []
for _ in range(m):
    maps.append(list(map(int,input().split())))

def bfs(start):
    visited = [[False] * n for _ in range(m)]
    queue = deque([[start[0],start[1],0]])
    visited[start[0]][start[1]] = True # 시작점 처리 제대로하기
    pre = 0
    end_point = start
    while queue:
        q = queue.popleft()
        qy, qx, cnt = q
        direct = ((-1, 0), (1, 0), (0, -1), (0, 1)) # 상 하 좌 우
        for i in range(4):
            dy, dx = direct[i]
            y = qy + dy
            x = qx + dx
            if 0 <= y < m and 0 <= x < n and visited[y][x] == False and maps[y][x] != 0:
                visited[y][x] = True
                queue.append((y, x, cnt + 1))
                if cnt + 1 > pre:
                    pre = cnt + 1
                    end_point = (y, x)
    return pre, end_point

rooms = [(y, x) for y in range(m) for x in range(n) if maps[y][x] != 0]

max_cnt = float('-inf')
tmps = []
if rooms:
    for start_point in rooms:
        cnt, end_point = bfs(start_point)
        if end_point:
            path_sum = maps[start_point[0]][start_point[1]] + maps[end_point[0]][end_point[1]]
            if cnt > max_cnt:
                max_cnt = cnt
                tmps = [(path_sum, cnt)]
            elif cnt == max_cnt:
                tmps.append((path_sum, cnt))
    tmp = sorted([i for i in tmps if i[1] == max_cnt], reverse=True)
    print(tmp[0][0])
else:
    print(0)

 

근데 틀림 아오

나중에 다시 또풀어야지

 

25.04.01 재풀이

 

시작부분과 끝부분의 합이 커야한다는 조건이 중요하다.

아무리 bfs 를 구현잘해도 해당 조건을 무시하면 제대로 구현 안됨

 

visited 로 방문했던 노드들을 최장으로 만들어간다.

 

import sys
from collections import deque
input = sys.stdin.readline

N,M = map(int,input().split())
maps = []

for i in range(N):
     maps.append(list(map(int,input().split())))
directions = ((0,1),(0,-1),(1,0),(-1,0))

def bfs(sy,sx):
    queue = deque([[sy,sx]])
    visited = [[-1] * M for _ in range(N)]
    visited[sy][sx] = 0

    max_sum = maps[sy][sx] * 2 # 시작방과 끝 방은 동일할 수 있다.
    max_dist = 0

    while queue:
        qy,qx = queue.popleft()
        for i in range(4):
            ny = qy + directions[i][0]
            nx = qx + directions[i][1]
            if 0 <= ny < N and 0 <= nx < M and visited[ny][nx] == -1 and maps[ny][nx] != 0:
                visited[ny][nx] = visited[qy][qx] + 1
                queue.append([ny,nx])
                if visited[ny][nx] > max_dist:
                    max_dist = visited[ny][nx]
                    max_sum = maps[sy][sx] + maps[ny][nx] # [페이크포인트] 시작 좌표와 가장 먼 거리(최장거리)에 위치한 좌표의 값의 합
                elif visited[ny][nx] == max_dist:
                    max_sum = max(max_sum,maps[sy][sx] + maps[ny][nx]) # [페이크포인트] 시작 좌표와 가장 먼 거리(최장거리)에 위치한 좌표의 값의 합

    return max_sum, max_dist

# 최장거리일때 max값 구하면됨
total_max_sum = 0
total_max_dist = 0
for i in range(N):
    for j in range(M):
        if maps[i][j] != 0:
            sum_, dist_ = bfs(i,j)
            if dist_ > total_max_dist:
                total_max_dist = dist_
                total_max_sum = sum_
            elif dist_ == total_max_dist:
                total_max_sum = max(sum_,total_max_sum)
print(total_max_sum)

 

최장거리일때, 합이 같으면 합이 큰것 확인하는 조건절도 제대로 확ㅇ니하자..........

꼭 한번 더 풀어봐야함

---

※ 알아야 할 것

• BFS에서 시작점 방문 체크 누락
  visited[start] = True 처리를 안 해줘서 중복 방문 발생 가능성 있음
  → BFS에서는 시작점도 반드시 visited 처리해야 한다
• visited 방식 개선
  기존에는 방문 여부를 True/False로만 저장했지만,
  수정 후에는 **최단 거리를 저장하는 visited 배열 (visited[y][x] = 거리)**을 사용
  → 이 방식은 도달 거리 비교 및 조건 분기 처리에 더 유용하고 확장성 있음
• 조건에서 “임의의 방”이면 전체 방 순회를 기본으로 생각해야 함