[SWEA] D4. 미로1

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE&problemTitle=%EB%AF%B8%EB%A1%9C&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

 

1. 해결방법

전형적인 BFS문제이다.

1. 방문체크 2차원 배열과 동서남북 이동 리스트를 생성.
2. 출발지점이 다를 수 있다고 가정하여 2중 for문으로 스타트 지점을 찾고 방문 체크한다.
3. bfs를 돌면서 방문이 안되었고, 입력 2차원 배열에서 벽(1)이 아니라면 방문 체크하고 q에 넣는다.

 

 

2. 정답코드

from collections import deque


input = sys.stdin.readline

# T = int(input())
T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    maps = [list(map(int, input().strip())) for _ in range(16)]
    chk = [[0] * 16 for _ in range(16)]
    dy, dx = (0, 1, 0, -1), (1, 0, -1, 0)

    # bfs
    def bfs(y, x):
        global answer

        q = deque()
        q.append(((y, x)))

        while q:
            ey, ex = q.popleft()
            if maps[ey][ex] == 3:
                answer = 1
                break
            for k in range(4):
                ny, nx = ey + dy[k], ex + dx[k]
                if 0 <= ny < 16 and 0 <= nx < 16:
                    if chk[ny][nx] == False and maps[ny][nx] != 1:
                        chk[ny][nx] = True
                        q.append((ny, nx))




    flag = False
    for i in range(16):
        for j in range(16):
            if maps[i][j] == 2:
                y, x = i, j
                chk[i][j] = True
                flag = True
                break
        if flag == True:
            break

    answer = 0
    bfs(y, x)

    print(f'#{test_case} {answer}')