[Python] 백준 4963 & 백준 1726

# 백준 4963

from collections import deque
import sys
input = sys.stdin.readline
queue = deque()

dx = [1, -1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, -1, 1, -1, 1, 1, -1]
def bfs(i, j):
    queue.append([i, j])
    graph[i][j] = 0
    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0<= ny < m and graph[nx][ny] == 1:
                queue.append([nx, ny])
                graph[nx][ny] = 0

while True:
    m,n = map(int, input().split())
    if m == 0 & n == 0:
        break
    graph = [list(map(int, input().split())) for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                bfs(i, j)
                cnt += 1
    print(cnt)

 

 

# 1726

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
sx, sy, sd = map(int, input().split())
ex, ey, ed = map(int, input().split())
visited = [[[False for _ in range(5)] for _ in range(m)] for _ in range(n)]

def change_dir(before, after):
    if before == after:
        return 0
    elif (before, after) == (1, 2) or (before, after) == (2, 1) or (before, after) == (3, 4) or (before, after) == (4, 3):
        return 2
    else:
        return 1

def bfs(i, j, dir, visited):
    dx = [0, 0, 0, 1, -1]
    dy = [0, 1, -1, 0, 0]

    q = deque()
    q.append((i, j, dir, 0))
    visited[i][j][dir] = True

    while q:
        x, y, dir, cnt = q.popleft()

        if x == ex - 1 and y == ey - 1:
            return cnt + change_dir(dir, ed)

        for i in range(1, 4):  # 1 ~3 칸 전진
            nx = x + dx[dir] * i
            ny = y + dy[dir] * i
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny][dir]:  # 해당 코드 추가안하면 메모리초과
                continue
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] != 1:
                visited[nx][ny][dir] = True
                q.append((nx, ny, dir, cnt + 1))
            else:  # 벽을 만나면 전진 멈춤
                break

        for i in range(1, 5):  # 방향 바꾸기
            if not visited[x][y][i]:
                visited[x][y][i] = True
                q.append((x, y, i, cnt + change_dir(dir, i)))


print(bfs(sx - 1, sy - 1, sd, visited))

 

로봇문제 증말 어려웠다ㅠㅠ 정답은 나오는데 계속 틀려서 구글링으로 힌트 얻고 통과..ㅠㅠ

queue에 cnt를 넣어주는게 포인트!