[PCCP] 1회차 : 배열 이동&탐색 문제

교육 프로그램명 : 혁신융합대학 프로그래머스 PCCP(Python) 대비 교육

교육 일시 : 2023.08.21 10:00~15:00

강사명 : 김태원 강사님

 

 

1. 4/8방향 탐색

2. 90도 회전이동

---

1. 4/8 방향 탐색

4방향 탐색 (출처 : 프로그래머스 교육 자료)

- row 방향, col 방향 이동 pair list 생성하기

- 4방향 탐색

# 위 / 오 / 아래 / 왼 => 시계방향 회전

dr=[-1, 0, 1, 0]    #행방향 이동
dc=[0, 1, 0, -1]    #열방향 이동

 

- 8방향 탐색

# 위 / 대각선 / 오 / 대각선 아래 / 대각선 / 왼 / 대각선 => 시계방향 회전 

dr = [-1, -1, 0, 1, 1, 1, 0, -1]   #행방향 이동
dc = [0, 1, 1, 1, 0, -1, -1, -1]]   #열방향 이동

 

 

- 도전문제 : 위험지대

https://school.programmers.co.kr/learn/courses/30/lessons/120866

프로그래머스

 

[solution 1]

- board[i][j] 각각에 대하여 안전지대인지 확인

- 8방향 중 폭탄이 있는 칸이 존재하면 위험지대로 판단하고 바로 break

def solution(board):
    answer = 0
    dr=[-1, -1, 0, 1, 1, 1, 0, -1]
    dc=[0, 1, 1, 1, 0, -1, -1, -1]
    
    for r in range(len(board)): #행 개수
        for c in range(len(board[0])): #열 개수
            flag=1
            if board[r][c] == 1:
                flag=0
            else:
                for i in range(8):
                    nr=r+dr[i]
                    nc=c+dc[i]
                    if 0<=nr and nr<len(board[0]) and 0<=nc and nc<len(board):
                        if board[nr][nc] == 1:
                            flag=0
                            break
            answer+=flag
    return answer

 

[solution 2]

- 전체 칸 중에서 위험지대인 칸의 개수 빼기

- 폭탄을 만날 때마다 인근 위험지역의 개수 세기

- 위험 지역이라고 판단된 위치를 2로 전환. 이때 기존에 0이었던 위치만 2로 바꾸고 폭탄이 있는 위치는 그대로 유지

def solution(board):
    dr=[-1, -1, 0, 1, 1, 1, 0, -1]
    dc=[0, 1, 1, 1, 0, -1, -1, -1]
    
    count=0
    for r in range(len(board)):
        for c in range(len(board[0])):
            if board[r][c] == 1:
                count+=1
                board[r][c]=2
                for i in range(8):
                    nr=r+dr[i]
                    nc=c+dc[i]
                    if 0<=nr and nr<len(board[0]) and 0<=nc and nc<len(board) and board[nr][nc]==0:
                        count+=1
                        board[nr][nc]=2
            
    return len(board)*len(board) - count

 

- 도전문제 : 공원 산책

https://school.programmers.co.kr/learn/courses/30/lessons/172928

프로그래머스

- 4방향 이동 list뿐만 아니라 방향 입력 문자에 대한 dictionary도 사용

- 기본거리 1에 대하여 전체 이동거리를 곱해주는 방향으로 2이상의 거리 이동

def solution(park, routes):
    #방향 list와 dictionary
    dr=[-1, 0, 1, 0]
    dc=[0, 1, 0, -1]
    direc_dic = {'N':0, 'E':1, 'S':2, 'W':3}
    
    #시작 위치 'S' 찾기
    parks=[list(street) for street in park]
    for i in range(len(parks)):
        for j in range(len(parks[0])):
            if parks[i][j] == 'S':
                r, c = i, j
                break

    #로봇 움직이기
    for i in routes:
        direc, dist = i.split(" ")
        flag=True	#이동 가능한지 지표
        
        # dist만큼 될때까지 하나씩 움직여보면서 확인해야함
        for l in range(int(dist)):
            nr = r + dr[direc_dic[direc]]*(l+1)
            nc = c + dc[direc_dic[direc]]*(l+1)

            #이동 과정에 배열을 벗어나거나 or X를 지나가야 된다면
            if 0>nr or nr>=len(parks) or 0>nc or nc>=len(parks[0]) or parks[nr][nc] == 'X':
                flag=False
                break
        if flag:
            r=nr
            c=nc   
    
    return [r, c]

 

 

 

 

 

2. 90도 회전이동

- 4/8방향 탐색에서 시계방향으로 리스트 정의

# 위 / 오 / 아래 / 왼 => 시계방향 회전

# 위 / 대각선 / 오 / 대각선 아래 / 대각선 / 왼 / 대각선 => 시계방향 회전 

 

- 나머지 계산으로 90도/45도 회전

※ python에서는 -1을 4로 나눈 나머지가 3으로 나오지만, 다른 언어에서는 불가능 

direc=(direc+1)%4  #시계 방향으로 90도 회전

direc=(direc-1)%4  #반시계 방향으로 90도 회전
direc=(direc+3)%4  #반시계 방향으로 90도 회전

 

- 연습문제 : 로봇의 이동 

def solution(moves):
    #위 오른쪽 아래 왼쪽 = 시계방향
    dr=[-1, 0, 1, 0] #행방향 이동
    dc=[0, 1, 0, -1] #열방향 이동
    
    direc=1
    r, c= 0, 0
    for command in moves:
        if command == 'G':
            nr=r+dr[direc]
            nc=c+dc[direc]
            if 0<=nr and nr<100 and 0<=nc and nc<100:
                r=nr
                c=nc
        elif command == 'R':
            #시계 방향으로 우회전
            direc=(direc+1)%4
        elif command == 'L':
            #시계 방향으로 좌회전
            direc=(direc-1)%4

    return [r,c]

 

 

- 도전 문제 : 정수를 나선형으로 배치하기

https://school.programmers.co.kr/learn/courses/30/lessons/181832

프로그래머스

 

[solution]

- (0,0)에서 시계방향으로 숫자를 채우는 나선 배열(달팽이 배열) 생성

- 배열 밖으로 벗어나거나, 장애물을 만나면 90도 방향회전

def solution(n):
    answer = [[0 for _ in range(n)] for _ in range(n)]
    dr=[-1, 0, 1, 0] #행방향 이동
    dc=[0, 1, 0, -1] #열방향 이동
    
    
    direc=1
    r, c= 0, 0
    count=1
    answer[0][0]=1

    while(count<n*n):
        nr=r+dr[direc]
        nc=c+dc[direc]
        
        #배열 범위 밖에 있거나 or 이미 값이 지정된 배열인 경우
        if 0>nr or nr>=n or 0>nc or nc>=n or answer[nr][nc] != 0: 
            #시계방향으로 90도 회전 
            direc=(direc+1)%4
            continue
                    
        r=nr
        c=nc
        count+=1
        answer[r][c]=count
    
    return answer