Can one bow before a king? Can one bow to a statue of a king?
For example, if one is visiting North Korea, may one bow to the statues as shown in this picture? Note that they are not fully prostrating themselves.
One is allowed to bow before a king, even a secular king.
Halacha does not forbid bowing to a king or, by extension, an important official in the king's court. In Tanach, we find a number of instances when prominent Jews bowed to kings, such as the prophet Natan bowing to David (Melachim 1:1:23) and Yosef's brothers bowing to Yosef (Bereishit 42:6). Yaakov even bowed to Eisav seven times. (Source)
Indeed, the reason Mordechai did not bow before Haman (Esther 3:2) was only because he was wearing an idol (Esther Rabba 7:6) or had made himself into a god (Rashi ad loc). We see, therefore, that one is allowed to bow before a human leader, and this is not considered idolatry.
It is unclear if the leaders of North Korea consider themselves to be "divine." Officially, North Korea is atheist, and most of the population has no religion. However, some websites assert that they do consider themselves as gods.
If one is under duress, he is permitted to bow to a statue of a king, as long as the statue is not an idol. However, it is not clear if one may bow if he is not under duress.
(There is discussion in the Rishonim regarding this issue, based on Daniel chapter 3. See Maharsha in his Chiddushei Aggadot on Megilla 12a, Tosafot on Pesachim 53b, as well as most of the Rishonim on Ketuvot 33b and Sanhedrin 74a. See also this article.)
In North Korea the ruling class is (strangely) treated like a deity according to this Wikipedia article similar to Nevuchadzezzar and the idol he built. As such, bowing is assur (even without prostration - pishut yadaim veraglayim). Even removing one's hat in deference is assur (cf Yoreh Deah 150:3 Rema)
If one is bowing down to a person who is not treated as a diety and is not wearing religious items to which he is also bowing, there is no problem. Bowing to another person in the east (and frequently in the Torah) was the equivalent of today's handshake and mode of showing respect and is by itself permissible.
Related story from here
Rav Chanoch Teller, in his biography of Rav Aharon Kotler, relates that Rav Aharon once was in a post office in Japan in 1940 when a siren sounded alerting that Emperor Hirohito was in the area. The law in Japan at that time was that anyone who did not bow to the ground when the siren sounded was to be put to death. Rav Aharon Kotler refused to bow down, invoking the precedent of Mordechai. Rav Aharon was beaten severely, but his life was spared. Similarly, my cousin Binyamin Toib z"l of Chadeira visited Rome in 1945 after serving in the Jewish Brigade of the British army in WWII. The Pope passed by, and everyone kneeled to the ground. However, Binyamin refused to kneel. The Pope's Swiss guards approached him and were ready to harm him until the Pope intervened when Binyamin explained that he was Jewish. Mr. Toib followed the example of Mordechai in his refusal to kneel to the Pope, even at risk to his life.
There is a chapter "Bowing" page 63 in the book "Letters to a Buddhist Jew" by Rabbis David Gottleib and Akiva Tatz that discusses at length this and similar issues.