김호쭈
DevForYou
김호쭈
전체 방문자
오늘
어제
  • 분류 전체보기 (321)
    • • 데이터베이스(DB) (9)
      • __SQL__ (9)
    • •알고리즘(Algorithm ) (117)
      • 문제풀이 (99)
      • 스터디 (14)
      • 알고리즘 팁 (4)
    • •Compter Science (57)
      • Operating System (25)
      • Computer Network (1)
      • Computer Vision (16)
      • Artificial Intelligence (14)
      • Software Technology (1)
    • • 독서 (36)
      • Design Pattern (24)
      • 객체지향의 사실과 오해 (1)
      • Object Oriented Software En.. (11)
    • • 개발 (26)
      • React (3)
      • node.js (6)
      • Django (11)
      • Spring boot (6)
    • • 개발Tip (4)
      • GitHub (0)
    • •프로젝트 (2)
      • 물물 (2)
    • •App (54)
      • 안드로이드 with Kotlin (50)
      • 코틀린(Kotiln) (4)
    • •회고 (8)
    • •취준일기 (3)
    • • 기타 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • GitHubDesktop
  • ㄱ
  • Remote저장소
  • 원격저장소
  • KMU_WINK
  • 깃허브데스크탑
  • local저장소
  • 로컬저장소

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
김호쭈

DevForYou

[백준17070&파이썬] State를 통해서 파이프의 이동방향을 다각화 하기
•알고리즘(Algorithm )/문제풀이

[백준17070&파이썬] State를 통해서 파이프의 이동방향을 다각화 하기

2023. 6. 6. 00:37

# 문제

백준 17070 파이프 옮기기1 파이썬 풀이

 

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의

www.acmicpc.net

# 코드

import sys

def print2D(arr) :
  for i in arr :
    print(i)

N = int(sys.stdin.readline().strip())
board = list()

for _ in range(N) :
  line = list(map(int,sys.stdin.readline().split()))
  board.append(line)

# 파이프를 계속 바꿔가면서 board를 바꾸어야 하기 때문에 백트래킹을 쓰는게 적합할거 같다

# PIPE #
PIPE_HORI = 0 # 가로
PIPE_VERT = 1 # 세로
PIPE_DIAG = 2 # 대각
HORI = [(0,1,PIPE_HORI)] # 가로
VERT = [(1,0,PIPE_VERT)] # 세로
DIAG = [(0,1,PIPE_DIAG),(1,0,PIPE_DIAG),(1,1,PIPE_DIAG)] # 대각
PIPE_DIRS = [
  [HORI,DIAG], # 가로인 경우
  [VERT,DIAG], # 세로인 경우
  [HORI,VERT,DIAG] # 대각인 경우
]
# ---- #

# 초기 상태 #
board[0][0] = -1
board[0][1] = -1
result = 0

dp = [ [0] * (N)for _ in range(N)]

if board[N-1][N-1] == 1 :
  print(0)
  exit()

def dfs(row, col, state) :
  global result,board

  checks = PIPE_DIRS[state]
  for check in checks :
    isCanGo = True
    movepoint = (-1,-1,-1)

    for dir in check :
      next = (row + dir[0] , col + dir[1])
      if 0 <= next[0] < N and 0 <= next[1] < N : # 범위 안이면서
        if board[next[0]][next[1]] == 0 : # 이동가능한 지점 0이면 이동이 가능하다
          movepoint = (next[0], next[1], dir[2])
        else :
          isCanGo = False
          break
      else :
        isCanGo = False
        break

    if isCanGo : # 이동이 가능하다면 여기서 이동을 시켜야 한다.
      # print(f"!!GO!! : {movepoint}")
      if movepoint[0] == N-1 and movepoint[1] == N-1 :
        result+=1
        return

      if movepoint[2] == PIPE_DIAG : # 대각 이동일 경우 visit를 다르게 해결해야한다.
        # 방문 처리
        board[movepoint[0]][movepoint[1]] = -1
        board[movepoint[0]-1][movepoint[1]] = -1
        board[movepoint[0]][movepoint[1]-1] = -1
        dfs(movepoint[0], movepoint[1], movepoint[2])
        board[movepoint[0]][movepoint[1]] = 0
        board[movepoint[0] - 1][movepoint[1]] = 0
        board[movepoint[0]][movepoint[1] - 1] = 0
      else :
        board[movepoint[0]][movepoint[1]] = -1 # 방문 처리
        dfs(movepoint[0],movepoint[1],movepoint[2])
        board[movepoint[0]][movepoint[1]] = 0  # 방문 처리 지우기

dfs(0,1,PIPE_HORI)
print(result)

# 풀이

  • 간단한 백트래킹을 이용한 구현 문제이다. 
  • 파이프의 상태와, 상태별 체크해야할 곳과 체크가 모두 성공할 시 해당하는 곳으로 이동하도록 하는 백트래킹 코드를 작성했다.
  • dfs코드가 수행되면 현재 파이프의 state(가로,세로,대각선)에 따라서 이을 수 있는 파이프가 결정된다.
  • 파이프가 체크가 완료됐다면, 해당하는 곳으로 이동해야 한다. 이때 방문처리를 해야하는데, 대각일 경우는 3곳을 방문처리 해줘야 한다.
  • 이걸 별도의 코드를 작성하지 않고 해결하기 위해서 movepoint라는 변수를 하나 두고, movepoint로 부터 대각일 경우는 위(-1,0) 옆(0,-1)에 대해서 방문처리를 한 후 dfs로 방문을 하도록 했다.
  • python3로 제출하면 시간초과가 발생한다. 코드 최적화(?)없이 pypy3로 제출했을때도 시간초과가 발생했고 시간을 줄이기 위해서 최적화를 수행했다.
  • 먼저 dfs()함수가 리턴(return)을 함수 진입후 체크하는 것이 아니라 진입전, movepoint를 통해서 다음 이동위치가 [N-1][N-1] 최종 도착지면 dfs를 호출하지 않도록 하고 거기서 result를 1 더해줬다.
  • 그 다음 state를 통해서 이동가능한 곳을 check할때 isCanGo를 활용했는데, 이때 False라면 바로 반복문을 break하도록 했다. (이건 사실 얼마 차이 안날거라고 생각했는데.. )

  • 여튼 그렇게 하니까 진짜 기적적으로 956ms로 통과했다. 해당 문제의 TC는 1초인데 아슬아슬하게 통과해서 기분 좋았다.

 

# 참고

  • 문제를 해결하고 나니까 DP를 이용한 풀이가 가능할거라는 생각이 들었다. DFS로 최종 도착지에 도착했다면 거쳐온 길들에 +1을 해주고, 새롭게 판 길에서 1이상의 이미 개척된 길을 마주한다면 그 길의 값을 다시 더해서 반환한다. 그리고 최종적으로 출발지(0,1)의 값을 반환시키면 DP를 이용한 풀이가 가능할거 같았다.
저작자표시 (새창열림)

'•알고리즘(Algorithm ) > 문제풀이' 카테고리의 다른 글

[백준9935&파이썬] 리스트 슬라이싱은 느리다. 문자열문제는 스택을 생각해보자  (0) 2023.06.08
[백준1043&파이썬] 적절한 자료구조 사용하기, 방문처리를 통해 무한루프에 빠지지 않게 하기  (0) 2023.06.06
[백준12865&파이썬] 0-1 냅색문제(배낭문제)  (0) 2023.06.05
[백준11054&파이썬] dp를 두번 이용하여 문제를 해결하자  (1) 2023.06.03
[백준11053&파이썬] DP를 이용하여 반복문을 하나 줄일 수 있다.  (0) 2023.06.01
    '•알고리즘(Algorithm )/문제풀이' 카테고리의 다른 글
    • [백준9935&파이썬] 리스트 슬라이싱은 느리다. 문자열문제는 스택을 생각해보자
    • [백준1043&파이썬] 적절한 자료구조 사용하기, 방문처리를 통해 무한루프에 빠지지 않게 하기
    • [백준12865&파이썬] 0-1 냅색문제(배낭문제)
    • [백준11054&파이썬] dp를 두번 이용하여 문제를 해결하자
    김호쭈
    김호쭈
    공부하고 정리하고 기록하기

    티스토리툴바