[백준] 소코반 복기

김지민·2022년 6월 17일
0

알고리즘

목록 보기
6/8
post-thumbnail

1. 문제

https://westmino.tistory.com/79

2. 아이디어

상황을 나누어서 생각하기
이동할 수 있는 경우와 불가능한 경우를 나누기

[이동 가능한 경우]
1) 이동 지점이 빈 공간이 경우
2) 이동 지점이 박스이고, 박스 이동 지점이 비어있거나 목표 위치인 경우

[이동 불가능한 경우]
1) 이동 지점이 벽인 경우
2) 이동 지점이 박스이고, 박스 이동 지점에 다른 박스가 존재하거나 벽인 경우

이동이 가능하면

[사람 위치 변경]
사람이 존재하는 자리에는 빈 자리이거나 목표 지점이다.
1) 현재 위치가 "w" 인 경우
현재 위치를 "+"로 바꿔준다.

2) 현재 위치가 "W" 인 경우
현재 위치를 "."로 바꿔준다.

[이동 위치 변경]
1) 이동 위치가 "." 인 경우
이동 위치를 "w"로 바꿔준다.

2) 이동 위치가 "#" 인 경우
이동 위치를 "W"로 바꿔준다.

3) 이동 위치가 "b" 또는 "B"인 경우

  • "b" 인 경우는 이동 위치를 "w"로 바꿔준다.

  • "B" 인 경우는 이동 위치를 "W"로 바꿔준다.

    박스 밀어주기

    • 박스 이동 지점이 "." 인 경우는 이동 위치를 "b"로 바꿔준다.
    • 박스 이동 지점이 "#" 인 경우는 이동 위치를 "B"로 바꿔준다.

3. 코드

import copy

dxy = dict()
dxy["U"] = [-1,0]
dxy["D"] = [1,0]
dxy["L"] = [0,-1]
dxy["R"] = [0,1]


def solution(R, C,round):
    graph = []
    goal = []
    box_cnt = 0
    flag = False
    for  i in range(R):
        lists = list(map(str, input()))
        graph.append(lists)
        for j in range(len(lists)):
            if graph[i][j] == "w" or graph[i][j] == "W":
                x = i
                y = j

            if graph[i][j] == "W" or graph[i][j] == "B" or graph[i][j] == "+":
                goal.append([i,j])

    
            if graph[i][j] == "b" or graph[i][j] == "B":
                box_cnt += 1
            
            
    move_lists = list(map(str, input()))



    for k in move_lists:
        # print(k,x,y)
        # for g in graph:
        #     print("".join(g))   
        # print()

    

        nx, ny = x + dxy[k][0], y+dxy[k][1]
        bx, by = nx +dxy[k][0], ny+dxy[k][1]

        if graph[nx][ny] == "#":
            continue
        elif graph[nx][ny] in "bB":
            if graph[bx][by] in "bB#":
                continue
       
        if graph[x][y] == "W":
            graph[x][y] = "+"
        
        elif graph[x][y] =="w":
            graph[x][y] = "."

        if graph[nx][ny] == ".": # 빈공간이면 이동
            graph[nx][ny] = "w"
            x,y = nx, ny
        
        elif graph[nx][ny] == "+":
            graph[nx][ny] = "W"
            x,y = nx, ny
        
        
        elif graph[nx][ny] == "B":
            graph[nx][ny] = "W" # 원래 자리 바꿔주기
            if graph[bx][by] == ".":
                graph[bx][by] = "b"
            elif graph[bx][by] == "+":
                graph[bx][by] = "B"
            x,y = nx, ny
        
        elif graph[nx][ny] == "b":
            graph[nx][ny] = "w" # 원래 자리 바꿔주기
            if graph[bx][by] == ".":
                graph[bx][by] = "b"
            elif graph[bx][by] == "+":
                graph[bx][by] = "B"
            x,y = nx, ny
        
        goal_cnt = 0
        for gx, gy in goal:
            if graph[gx][gy] == "B":
                goal_cnt += 1

        if goal_cnt == box_cnt:
            flag= True
            print("Game %d: complete" %(round))
            for g in graph:
                print("".join(g))
            break
        
    if not flag:
        print("Game %d: incomplete" %(round))
        for g in graph:
            print("".join(g))


round = 0
while True:
    a,b  = map(int, input().split())
    round += 1
    if a == 0 and b == 0:
        break
    else:
        solution(a,b, round)

4. 오답 노트

  1. [기준을 제대로 세우지 못함] 이동 가능한 경우와 가능하지 않는 경우를 정확하게 파악하고 나눠주어야 했음
  2. [오타] 좌표가 여러개이다 보니 x,y를 바꿔 쓰는 경우가 있음 수시로 확인이 필요함
  3. [기준을 제대로 세우지 못함] 모든 경우이 수를 가정하고 사람이 이동한 자리에는 어떻게 표시해야 할지 정확한 파악이 필요함
  4. [검사 위치를 제대로 세우지 못함] 모든 연산이 끝난 이후에 검사해주어야 한다.
profile
💡Habit is a second nature. [Git] https://github.com/Kimjimin97

0개의 댓글