developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 통계학
  • 데이터분석
  • ARIMA모형
  • 운영체제인터럽트
  • 삼성코테파이썬준비
  • BOJ파이썬풀이
  • 삼성코테구현풀이
  • AR모형
  • Arima
  • 삼성코테자바풀이
  • 삼성코테구현문제추천
  • 삼성코테준비
  • 카카오코테
  • 삼성코테기출
  • c++디자인패턴
  • MA모형
  • c++ 빌더 패턴
  • 삼성코테파이썬풀이
  • SW역량테스트파이썬
  • 통계분석
  • 시계열분석
  • 삼성코테자바준비
  • 삼성코테자바꿀팁
  • 삼성코테기출자바풀이
  • SW역량테스트파이썬풀이
  • 백준파이썬풀이
  • 코테파이썬
  • 카카오코테java풀이
  • 삼성코테파이썬
  • 시계열

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 새로운 게임2 17837번 (python)

2021. 10. 18. 13:45

❓ 문제 - 백준 새로운 게임2 17837번 - python 풀이법

 

출처 

(https://www.acmicpc.net/problem/17837)

 

17837번: 새로운 게임 2

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하

www.acmicpc.net

 

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

  • board 리스트를 통해 보드의 정보를 입력받고, horse 리스트에 말의 위치(x,y) 방향(d)의 정보를 입력받고, chess 리스트를 통해서 현재 체스판에 행과 열에 놓여져 있는 말의 번호를 저장한다.
  • solve() 함수를 통해 모든 말에 대해서 이동을 수행한 후 count 1 증가 시켜주고 턴의 횟수, 즉 count가 1000번이 넘으면 게임을 강제로 종료시킨다. 또한 말을 이동하면서 solve 함수를 통해 False값이 반환되면(말이 한 체스판의 위치에서 4마리 이상 쌓아짐) count를 출력한 후 게임을 종료한다.

2. solve()

  • 이동했을 때 체스판의 범위를 넘거나 칸이 파란색인 경우 동일하게 처리할 수 있도록 구현하는데, change_dir() 함수를 통해 방향을 바꿔주고 방향을 바꾼 곳으로 한 칸 더 이동했을 때 또 다시 범위를 넘거나 파란색 칸이면 말을 이동하지 않는다.
  •  이동하기 전 현재위치에서 chess 리스트를 사용하여 horse_up 리스트를 통해 현재 이동하려는 말 ~ 그 위에 쌓아져있는 말에 대한 정보를 저장한다. 또한 말을 이동하기 위해서 chess 리스트에서 현재 이동하려는 말 ~ 그 위에 쌓아져있는 말에 대한 번호를 지운다.
  •  만약 이동하려는 위치가 빨간색 칸이면 horse_up 리스트에 들어있는 말의 정보를 한칸씩 뒤로 움직인다.
  • 이동하려는 위치 nx, ny에 horse_up 리스트로 현재 이동하려는 말 ~ 그 위에 쌓아져 있는 말의 번호를 chess판에 넣어주고, horse 리스트에 이동된 말들의 위치 정보를 변경해준다.
  • 이동이 끝났을 때 만약 이동된 곳에 말이 4개 이상 쌓아져 있다면 게임을 종료할 수 있게 False를 반환한다.

 

 

💻 소스코드

n, k = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
chess = [[[] for _ in range(n)] for _ in range(n)]
# 동 - 서 - 북 - 남
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
horse = []

for i in range(k):
    x, y, d = map(int, input().split())
    horse.append([x-1, y-1, d-1])
    chess[x-1][y-1].append(i)

count = 0

def change_dir(d):
    if d in [0, 2]:
        d += 1
    elif d in [1, 3]:
        d -= 1
    return d

def solve(h_num):
    x, y, d = horse[h_num]
    nx = x + dx[d]
    ny = y + dy[d]
    if 0 > nx or nx >= n or 0 > ny or ny >= n or board[nx][ny] == 2:
        d = change_dir(d)
        horse[h_num][2] = d
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 > nx or nx >= n or 0 > ny or ny >= n or board[nx][ny] == 2:
            return True

    horse_up = []
    for h_idx, h_n in enumerate(chess[x][y]):
        if h_n == h_num:
            horse_up.extend(chess[x][y][h_idx:])
            chess[x][y] = chess[x][y][:h_idx]
            break

    if board[nx][ny] == 1:
        horse_up = horse_up[-1::-1]

    for h in horse_up:
        horse[h][0], horse[h][1] = nx, ny
        chess[nx][ny].append(h)

    if len(chess[nx][ny]) >= 4:
        return False
    return True

while True:
    what = False
    if count > 1000:
        print(-1)
        break
    for i in range(k):
        if solve(i) == False:
            what = True
            break
    count += 1
    if what:
        print(count)
        break

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 주사위 윷놀이 17825번 (python, JAVA)  (0) 2021.10.18
BOJ - 원판 돌리기 17822번 (python)  (0) 2021.10.18
BOJ - 게리맨더링2 17779번 (python, JAVA)  (0) 2021.10.17
BOJ - 연구소 3 17142번 (python)  (0) 2021.10.17
BOJ - 이차원 배열과 연산 17140번 (python)  (0) 2021.10.17
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 주사위 윷놀이 17825번 (python, JAVA)
    • BOJ - 원판 돌리기 17822번 (python)
    • BOJ - 게리맨더링2 17779번 (python, JAVA)
    • BOJ - 연구소 3 17142번 (python)
    developer-ellen
    developer-ellen

    티스토리툴바