토토백_학부 연구생 민상(21922)

문제

풀이

• BFS 사용
• 좌표 값이 1,2,3,4 의 경우에 따라 탐색 중지 or 좌표 case 변경(상,하,좌,우)
• 좌표 값이 9일 경우 탐색 중지(어차피 main 함수에서 중복되므로)
• haveToGo 라는 다음 탐색지를 누적하는 queue 와, curCase 라는 좌표 이동 방향을 나타내는 queue를 활용

코드

from collections import deque
import sys
sys.stdin = open("input.txt", "rt")
# 1은 좌 우로 올 경우 종료
# 2는 상 하로 올 경우 종료
# 3은 우에서 상으로, 하에서 좌로 / 좌에서 하로, 상에서 우로 = 좌표 변경 후 * (-1)
# 4는 우로에서 하로, 하에서 우로 / 좌에서 상으로, 상에서 좌로 = 좌표 변경
# recursion error 나니까 BFS 로 바꿔야 될 것 같다!
def BFS(haveToGo, visited, arr, curCase, row, col):
    while haveToGo:
        curPos = haveToGo.popleft()
        case = curCase.popleft()
        curY = curPos[0] + case[0]
        curX = curPos[1] + case[1]
        
        if row > curY >= 0 and col > curX >= 0:
            visited[curY][curX] = 1
            nextPos = (curY, curX)
            if arr[curY][curX] == 9:
                break
            if arr[curY][curX] == 1:
                visited[curY][curX] = 1
                # 좌우로(0,1) (0,-1) 오는 경우 종료, 상하는 진행
                if case == (1,0) or case == (-1, 0):
                    haveToGo.append(nextPos)
                    curCase.append(case)
                else:
                    break
            elif arr[curY][curX] == 2:
                visited[curY][curX] = 1
                # 상하로 오는 경우 종료, 좌우는 진행
                if case == (0,1) or case == (0, -1):
                    haveToGo.append(nextPos)
                    curCase.append(case)
                else:
                    break
            elif arr[curY][curX] == 3:   # "up","right" 으로 온 경우 / "down","left" 으로 온 경우 중복처리
                if "ur3" not in str(visited[curY][curX]) and (case == (-1, 0) or case == (0, 1)):
                    visited[curY][curX] = str(visited[curY][curX])+"ur3"
                    tmpCase = (case[1]*(-1), case[0]*(-1))
                    haveToGo.append(nextPos)
                    curCase.append(tmpCase)
                elif "dl3" not in str(visited[curY][curX]) and (case == (1, 0) or case == (0, -1)):
                    visited[curY][curX] = str(visited[curY][curX])+"dl3"
                    tmpCase = (case[1]*(-1), case[0]*(-1))
                    haveToGo.append(nextPos)
                    curCase.append(tmpCase)
                else:
                    break
            elif arr[curY][curX] == 4:   # "up","left" 으로 온 경우 / "down","right" 으로 온 경우 중복처리
                if "ul4" not in str(visited[curY][curX]) and (case == (-1, 0) or case == (0, -1)):
                    visited[curY][curX] = str(visited[curY][curX])+"ul4"
                    tmpCase = (case[1], case[0])
                    haveToGo.append(nextPos)
                    curCase.append(tmpCase)
                elif "dr4" not in str(visited[curY][curX]) and (case == (1, 0) or case == (0, 1)):
                    visited[curY][curX] = str(visited[curY][curX])+"dr4"
                    tmpCase = (case[1], case[0])
                    haveToGo.append(nextPos)
                    curCase.append(tmpCase)
                else:
                    break
            else:
                haveToGo.append(nextPos)
                curCase.append(case)

if __name__ == '__main__':
    row, col = map(int, input().split())
    arr = []
    std = []
    visited = list([0] * col for _ in range(row))
    # 이차원 배열 담기
    for i in range(row):
        arr.append(list(map(int, input().split())))
    # 에어컨이 있는 위치(9) 찾기
    for i in range(row):
        for j in range(col):
            if arr[i][j]== 9:
                std.append((i,j))
    # 에어컨 개수 만큼 BFS 반복 호출
    case = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    if len(std) == 0:
        print(0)
    else:
        for i in range(len(std)):
            visited[std[i][0]][std[i][1]] = 1
            for j in range(4):
                haveToGo = deque([std[i]])
                curCase = deque([case[j]])
                BFS(haveToGo, visited, arr, curCase, row, col)
            cnt = 0
        for i in range(row):
            # print(visited[i])
            for j in range(col):
                if visited[i][j] != 0:
                    cnt += 1
        print(cnt)

느낀점

• DFS가 식세우기 편해서 DFS로 코드를 짰는데 Recursion Error 가 나서 sys.setrecursionlimit(10**6) 을 했지만 Erorr 가 잡히지 않았다.
• 이후 BFS로 바꾸고 나서는 시간초과를 잡는데 오래 걸렸다.
• 조건식을 세우고 나니 별게 아니었다는 것을 느꼈다.
• 그래도 블로그 안찾아보고 gold 문제 풀어서 기분이 좋았다.