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

문제

풀이

• BFS를 활용한다
• 1, 2, 3, 4 의 경우에 따라 같던 길을 중복 탐색 하지 않도록 조건을 설정한다
• 다음 좌표로 이동할땐, 다음 좌표 값을 havweToGo queue 에 넣고 curCase queue에 증감 정도(상,하,좌,우)를 나타내는 좌표를 넣는다.
• 9의 경우에도 탐색하지 않도록 조건을 설정한다(어차피 main함수에서 또 탐색하므로)

코드

from collections import deque
import sys
sys.stdin = open("input.txt", "rt")
# 1은 좌 우 로 왔을 경우 break
# 2는 상 하 로 왔을 경우 break
# 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" 으로 온 경우 중복처리
                # visited[curY][curX] = 1
                # tmpCase = (case[1], case[0])
                # haveToGo.append(nextPos)
                # curCase.append(tmpCase)
                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 나서 Bfs로 바꿨다. 노드 문제 아니면, 왠만해선 BFS로 풀어야 한다고..
• 시간 초과 때문에 조금 고생했다.
  
• 그래도 다른 블로그 안보고 gold 문제 풀어서 기분이 좋다..